哈希算法题目：三数之和

字数 2105 2025-12-23 01:54:42

哈希算法题目：三数之和

题目描述
给你一个整数数组 nums，判断数组中是否存在三个不同的元素 a, b, c，使得它们的和 a + b + c = 0？请找出所有满足条件且不重复的三元组。

注意：答案中不能包含重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2], [-1,0,1]]

因为 (-1) + (-1) + 2 = 0 且 (-1) + 0 + 1 = 0
输出中的三元组 [-1,0,1] 和 [0,1,-1] 被视为重复，只保留一个

解题思路
最直接的暴力解法是三重循环枚举所有三元组，但时间复杂度为 O(n³)，且需要去重，效率很低。
这里采用 排序 + 双指针 + 哈希去重 的思路，可以优化到 O(n²)。
主要步骤如下：

排序：将数组升序排序，便于后续用双指针查找和跳过重复元素。
固定一个数：遍历数组，将当前数字 nums[i] 作为三元组的第一个数。
双指针找另外两个数：在 i 右侧的区间里，设置左指针 left = i+1 和右指针 right = n-1，通过比较三数之和与 0 的大小，移动指针。
跳过重复：在遍历过程中，如果遇到相同的数字，则跳过，避免重复解。
利用哈希集合去重（备选）：也可以使用集合记录两数之和的目标值，但需注意去重逻辑。

详细步骤讲解

假设数组为 nums = [-1, 0, 1, 2, -1, -4]。

步骤 1：排序
排序后数组为：[-4, -1, -1, 0, 1, 2]
排序的目的：

方便用双指针在有序数组上快速找到两数之和。
方便通过相邻元素比较来跳过重复的三元组。

步骤 2：外层循环固定第一个数
用下标 i 从 0 遍历到 n-3（因为后面至少需要两个数）。

第 1 轮：i = 0，固定 -4

需要在 [-1, -1, 0, 1, 2] 中找两数之和等于 4（因为 -4 + a + b = 0 即 a + b = 4）。
双指针：
- left = 1（值 -1），right = 5（值 2），和 = 1，小于 4 → left 右移。
- left = 2（值 -1），right = 5（值 2），和 = 1，小于 4 → left 右移。
- left = 3（值 0），right = 5（值 2），和 = 2，小于 4 → left 右移。
- left = 4（值 1），right = 5（值 2），和 = 3，小于 4 → left 右移，此时 left = 5，right = 5 停止。
没有找到和为 4 的组合，本轮无解。

步骤 3：去重技巧
在循环过程中，如果 nums[i] 和上一个固定的数相同，就跳过，因为相同的第一个数会产生重复的三元组。

第 2 轮：i = 1，固定 -1

检查 nums[1] 和 nums[0] 是否相同？-1 和 -4 不同，不跳过。
需要在 [-1, 0, 1, 2] 中找两数之和等于 1（因为 -1 + a + b = 0 即 a + b = 1）。
双指针：
- left = 2（值 -1），right = 5（值 2），和 = 1，等于目标 1 → 找到一个解 [-1, -1, 2]。
- 记录解后，left 右移、right 左移，并跳过重复值：
  - left 从 2 移到 3（值 0），right 从 5 移到 4（值 1）。
- 现在 left = 3（值 0），right = 4（值 1），和 = 1，等于目标 1 → 找到第二个解 [-1, 0, 1]。
- 继续移动指针，left 右移、right 左移，left = 4，right = 3，left >= right 停止。

第 3 轮：i = 2，固定 -1

检查 nums[2] 和 nums[1] 是否相同？都是 -1，跳过本轮，避免重复解。

第 4 轮：i = 3，固定 0

需要在 [1, 2] 中找两数之和等于 0（即 a + b = 0）。
双指针：left = 4（值 1），right = 5（值 2），和 = 3，大于 0 → right 左移，right = 4，停止，无解。

i 继续遍历，但后面不足三个数，停止。

最终结果：[[-1, -1, 2], [-1, 0, 1]]

时间复杂度与空间复杂度

排序：O(n log n)
外层循环 O(n)，内层双指针 O(n) → 总计 O(n²)
空间复杂度：O(1) 或 O(n)（取决于排序是否使用额外空间）

核心要点

先排序，将三数之和问题转化为两数之和问题（双指针）。
外层循环固定第一个数，内层用双指针在有序数组中找另外两个数。
去重方法：
- 当 nums[i] == nums[i-1] 时，跳过当前 i。
- 找到一组解后，移动左右指针时，跳过与当前值相同的元素。

这样就能在 O(n²) 时间内高效找到所有不重复的三元组。

哈希算法题目：三数之和题目描述给你一个整数数组 nums ，判断数组中是否存在三个不同的元素 a, b, c ，使得它们的和 a + b + c = 0 ？请找出所有满足条件且不重复的三元组。注意：答案中不能包含重复的三元组。示例：因为 (-1) + (-1) + 2 = 0 且 (-1) + 0 + 1 = 0 输出中的三元组 [-1,0,1] 和 [0,1,-1] 被视为重复，只保留一个解题思路最直接的暴力解法是三重循环枚举所有三元组，但时间复杂度为 O(n³)，且需要去重，效率很低。这里采用排序 + 双指针 + 哈希去重的思路，可以优化到 O(n²)。主要步骤如下：排序：将数组升序排序，便于后续用双指针查找和跳过重复元素。固定一个数：遍历数组，将当前数字 nums[i] 作为三元组的第一个数。双指针找另外两个数：在 i 右侧的区间里，设置左指针 left = i+1 和右指针 right = n-1 ，通过比较三数之和与 0 的大小，移动指针。跳过重复：在遍历过程中，如果遇到相同的数字，则跳过，避免重复解。利用哈希集合去重（备选）：也可以使用集合记录两数之和的目标值，但需注意去重逻辑。详细步骤讲解假设数组为 nums = [-1, 0, 1, 2, -1, -4] 。步骤 1：排序排序后数组为： [-4, -1, -1, 0, 1, 2] 排序的目的：方便用双指针在有序数组上快速找到两数之和。方便通过相邻元素比较来跳过重复的三元组。步骤 2：外层循环固定第一个数用下标 i 从 0 遍历到 n-3（因为后面至少需要两个数）。第 1 轮：i = 0，固定 -4 需要在 [-1, -1, 0, 1, 2] 中找两数之和等于 4 （因为 -4 + a + b = 0 即 a + b = 4 ）。双指针： left = 1 （值 -1）， right = 5 （值 2），和 = 1，小于 4 → left 右移。 left = 2 （值 -1）， right = 5 （值 2），和 = 1，小于 4 → left 右移。 left = 3 （值 0）， right = 5 （值 2），和 = 2，小于 4 → left 右移。 left = 4 （值 1）， right = 5 （值 2），和 = 3，小于 4 → left 右移，此时 left = 5 ， right = 5 停止。没有找到和为 4 的组合，本轮无解。步骤 3：去重技巧在循环过程中，如果 nums[i] 和上一个固定的数相同，就跳过，因为相同的第一个数会产生重复的三元组。第 2 轮：i = 1，固定 -1 检查 nums[1] 和 nums[0] 是否相同？ -1 和 -4 不同，不跳过。需要在 [-1, 0, 1, 2] 中找两数之和等于 1（因为 -1 + a + b = 0 即 a + b = 1 ）。双指针： left = 2 （值 -1）， right = 5 （值 2），和 = 1，等于目标 1 → 找到一个解 [-1, -1, 2] 。记录解后， left 右移、 right 左移，并跳过重复值： left 从 2 移到 3（值 0）， right 从 5 移到 4（值 1）。现在 left = 3 （值 0）， right = 4 （值 1），和 = 1，等于目标 1 → 找到第二个解 [-1, 0, 1] 。继续移动指针， left 右移、 right 左移， left = 4 ， right = 3 ， left >= right 停止。第 3 轮：i = 2，固定 -1 检查 nums[2] 和 nums[1] 是否相同？都是 -1，跳过本轮，避免重复解。第 4 轮：i = 3，固定 0 需要在 [1, 2] 中找两数之和等于 0（即 a + b = 0 ）。双指针： left = 4 （值 1）， right = 5 （值 2），和 = 3，大于 0 → right 左移， right = 4 ，停止，无解。 i 继续遍历，但后面不足三个数，停止。最终结果： [[-1, -1, 2], [-1, 0, 1]] 时间复杂度与空间复杂度排序：O(n log n) 外层循环 O(n)，内层双指针 O(n) → 总计 O(n²) 空间复杂度：O(1) 或 O(n)（取决于排序是否使用额外空间）核心要点先排序，将三数之和问题转化为两数之和问题（双指针）。外层循环固定第一个数，内层用双指针在有序数组中找另外两个数。去重方法：当 nums[i] == nums[i-1] 时，跳过当前 i。找到一组解后，移动左右指针时，跳过与当前值相同的元素。这样就能在 O(n²) 时间内高效找到所有不重复的三元组。