哈希算法题目：三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足：

• i != j、i != k 且 j != k
• nums[i] + nums[j] + nums[k] == 0
  你需要返回所有不重复的三元组。

示例
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：

• nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
• nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
• 但 [-1,0,1] 和 [-1,0,1] 是重复的，最终只保留一个。

要求：

• 时间复杂度尽可能低
• 避免结果中出现重复的三元组

解题思路

1. 问题分析
   需要找到三个数，其和为0。最直接的方法是三重循环，但时间复杂度为 \(O(n^3)\)，且需要去重，效率很低。
2. 哈希表优化思路
   可以固定一个数 a，然后问题转化为：在剩余数组中寻找两个数 b 和 c，使得 b + c = -a。这便成了“两数之和”问题，可用哈希表优化。
3. 去重挑战
   直接使用哈希表可能产生重复三元组（如数组中有重复元素）。需通过排序 + 跳过重复元素来保证唯一性。
4. 最终方案
   • 对数组排序（时间复杂度 \(O(n \log n)\)）
   • 外层循环固定第一个数 nums[i]
   • 内层使用双指针法（而非哈希表）寻找另两个数，因为哈希表在去重时实现较复杂
   • 通过跳过相同元素来避免重复结果

逐步讲解

步骤1：排序

输入: nums = [-1, 0, 1, 2, -1, -4]
排序后: [-4, -1, -1, 0, 1, 2]

排序的目的：

• 方便跳过重复元素
• 为双指针法创造条件

步骤2：外层循环固定第一个数

设外层循环索引为 i，固定 nums[i] 为第一个数。

关键点：

• 如果 nums[i] > 0，由于数组已排序，后面的数都更大，三数之和不可能为0，直接结束循环。
• 如果 nums[i] == nums[i-1]，说明这个数字已经作为第一个数被考虑过，跳过以避免重复。

步骤3：内层双指针寻找另两个数

• 左指针 left = i + 1
• 右指针 right = n - 1
• 目标：找到 nums[left] + nums[right] == -nums[i]

三种情况：

1. 和等于目标值
   记录三元组 [nums[i], nums[left], nums[right]]
   然后移动左右指针，并跳过所有重复的 nums[left] 和 nums[right]
2. 和小于目标值
   说明需要更大的数，左指针右移（left++）
3. 和大于目标值
   说明需要更小的数，右指针左移（right--）

步骤4：实例推演

以排序后的数组 [-4, -1, -1, 0, 1, 2] 为例：

1. i=0, nums[i]=-4
   left=1, right=5, target=4
   -1+2=1 < 4 → left++
   -1+2=1 < 4 → left++
   0+2=2 < 4 → left++
   1+2=3 < 4 → left++（left=5, left>=right，停止）

2. i=1, nums[i]=-1
   left=2, right=5, target=1
   -1+2=1 == 1 → 记录 [-1, -1, 2]
   跳过重复：left++到3, right--到4
   left=3, right=4: 0+1=1 == 1 → 记录 [-1, 0, 1]
   left++到4, right--到3（left>right，停止）

3. i=2, nums[i]=-1
   由于 nums[2] == nums[1]，跳过（避免重复）

4. i=3, nums[i]=0
   left=4, right=5, target=0
   1+2=3 > 0 → right--（left=4, right=4，停止）

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

代码实现

def threeSum(nums):
    nums.sort()  # 排序
    n = len(nums)
    result = []
    
    for i in range(n - 2):  # i 最多到倒数第三个数
        # 跳过重复的第一个数
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # 如果第一个数大于0，后面的和不可能为0
        if nums[i] > 0:
            break
        
        left, right = i + 1, n - 1
        target = -nums[i]  # 需要找到 b + c = -a
        
        while left < right:
            current_sum = nums[left] + nums[right]
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                # 跳过重复的 left 和 right
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
                
    return result

复杂度分析

• 时间复杂度：\(O(n^2)\)
  排序 \(O(n \log n)\)，外层循环 \(O(n)\)，内层双指针 \(O(n)\)，总体 \(O(n^2)\)
• 空间复杂度：\(O(1)\)（不考虑存储结果的空间）

关键点总结

1. 排序：便于去重和双指针操作
2. 去重技巧：在外层循环跳过相同的 nums[i]，在内层移动指针时跳过相同值
3. 提前终止：当 nums[i] > 0 时直接结束
4. 双指针代替哈希表：哈希表虽能解决“两数之和”，但去重较麻烦；双指针在有序数组上更直观且节省空间

扩展思考

• 如果要求返回三元组的索引而非值，该如何修改？
• 如果数组非常大但范围有限（如全在 [-1000, 1000]），是否有更优解法？
• 如何修改算法以解决“四数之和”问题？