好的，我们这次来详细讲解 LeetCode 第 15 题：三数之和。

这道题是面试中的高频题，它不仅考察基本的编程能力，更考察对双指针技巧的灵活运用和对去重逻辑的严谨思考。

题目描述

题目链接： 15. 3Sum
难度：中等

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

• i != j、i != k 且 j != k
• nums[i] + nums[j] + nums[k] == 0

请你找出所有满足条件且不重复的三元组。

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

示例 1：

输入：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。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0。
但是，不同的三元组是 [-1,0,1] 和 [-1,-1,2]。注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三数之和不为 0。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三数之和为 0。

循序渐进式讲解

我们从一个最直观的想法开始，逐步优化，最终到达最高效的解法。

步骤一：最暴力的想法（三重循环）

我们最容易想到的方法是使用三重循环，枚举所有可能的三元组 (i, j, k)，检查它们的和是否为 0。

• 伪代码：

  初始化结果列表 result = []
  对 i 从 0 到 n-1：
      对 j 从 i+1 到 n-1：
          对 k 从 j+1 到 n-1：
              如果 nums[i] + nums[j] + nums[k] == 0：
                  将 [nums[i], nums[j], nums[k]] 加入 result
  返回 result
  

• 问题：

  1. 时间复杂度：O(n³)，当 n=3000 时，计算量巨大，会超时。
  2. 去重困难：例如输入 [-1, -1, 0, 1]，我们会得到两个 [-1, 0, 1]，因为第一个 -1 和第二个 -1 分别与 0, 1 组合都会满足条件。我们需要在结果中去掉重复的。

这个暴力解法在 LeetCode 上无法通过，我们必须寻找更优解。

步骤二：优化思路（使用哈希表）

我们回想一下简单的两数之和问题：给定一个数组和一个目标值，找出两个数之和等于目标值。我们可以用哈希表（Set）来将时间复杂度从 O(n²) 降低到 O(n)。

对于三数之和，我们可以将其转化为两数之和问题：

• 固定第一个数 a，那么问题就变成了：在剩下的数中，找到两个数 b 和 c，使得 b + c = -a。

• 伪代码：

  初始化结果集合 result_set = set() // 用集合来帮助去重
  对 i 从 0 到 n-1：
      a = nums[i]
      初始化一个哈希表 seen
      对 j 从 i+1 到 n-1：
          b = nums[j]
          c = -a - b // 我们需要的第三个数
          如果 c 在哈希表 seen 中：
              将三元组 [a, b, c] 排序后转化为元组，加入 result_set（为了去重）
          否则：
              将 b 加入哈希表 seen
  将 result_set 中的元组转化回列表，返回
  

• 进步与问题：

  • 时间复杂度：O(n²)，比三重循环好。
  • 问题：
    1. 去重依赖集合：我们通过将三元组排序后转为元组，利用集合的天然去重特性。这不是最优的，且转换操作有开销。
    2. 空间复杂度：需要额外的哈希表空间。

这个方法可以工作，但不够优雅，且在某些语言中处理去重比较麻烦。我们还有更好的方法。

步骤三：最优解法（排序 + 双指针）

这是解决此类问题的标准且高效的方案。核心思想是排序和双指针。

第一步：排序
首先将数组排序。排序的好处是：

1. 相同的数字会紧挨在一起，方便我们跳过重复元素，从而从根本上避免产生重复的三元组。
2. 有序数组为我们使用双指针技巧创造了前提。

第二步：遍历并固定第一个数
我们遍历数组，将当前元素 nums[i] 作为三元组的第一个数 a。

关键的去重操作1：如果 nums[i] 和它前一个数 nums[i-1] 相同，我们就跳过本次循环。因为以同一个 a 开头，找到的三元组肯定是重复的。

注意：这里比较的是 i 和 i-1，而不是 i 和 i+1。因为我们要避免的是使用相同的值作为开头，而不是避免使用相同的值作为第二个或第三个数。举个例子，[0,0,0] 是合法的，当我们固定第一个 0 时，已经找到了 [0,0,0] 这个解。当 i 移动到第二个 0 时，如果因为它和前面的 0 相同就跳过，那就错过了这个解吗？不会的，因为我们在第一个 0 时已经找到了。而如果我们因为和后面的 0 相同就跳过，那才会错过解。实际上，正确的逻辑是：if (i > 0 && nums[i] == nums[i-1]) continue; 这样，对于 [0,0,0]，当 i=0 时，不跳过；当 i=1 时，因为 nums[1] == nums[0]，所以跳过；当 i=2 时，因为 nums[2] == nums[1]，所以也跳过。这样就保证了我们只得到唯一解 [0,0,0]。

第三步：使用双指针寻找另外两个数
在 i 的右侧子数组中，我们定义两个指针：

• left 指针指向 i+1（子数组的左边界）。
• right 指针指向数组末尾 n-1（子数组的右边界）。

现在，我们的目标是找到 b 和 c，使得 a + b + c = 0，即 b + c = -a。

我们计算 sum = nums[left] + nums[right]：

• 如果 sum == target（即 -a）：
  • 我们找到了一个解 [a, nums[left], nums[right]]，将其加入结果列表。
  • 关键的去重操作2：然后，我们需要移动 left 和 right 跳过所有重复的值。执行 left++ 直到 nums[left] != nums[left-1]，同时执行 right-- 直到 nums[right] != nums[right+1]。这是为了确保下一个解不会是重复的。
  • 最后，再常规地移动一次指针（left++, right--）来寻找下一个可能的解。
• 如果 sum < target：
  • 说明总和太小了，我们需要增大它，所以将 left 指针向右移动（left++）。
• 如果 sum > target：
  • 说明总和太大了，我们需要减小它，所以将 right 指针向左移动（right--）。

第四步：循环直到指针相遇
双指针的查找过程一直进行，直到 left 和 right 相遇。

完整代码示例（Python）

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()  # 第一步：排序
        result = []
        
        # 第二步：遍历数组，固定第一个数
        for i in range(n - 2):  # 留出两个位置给 left 和 right
            a = nums[i]
            # 去重操作1：如果当前数已经作为第一个数处理过，则跳过
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            # 第三步：双指针查找
            left, right = i + 1, n - 1
            target = -a  # 我们需要 b + c = -a
            
            while left < right:
                current_sum = nums[left] + nums[right]
                
                if current_sum == target:
                    # 找到一个解
                    result.append([a, nums[left], nums[right]])
                    
                    # 去重操作2：跳过所有重复的 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:  # current_sum > target
                    right -= 1
                    
        return result

复杂度分析

• 时间复杂度：O(n²)。
  • 排序需要 O(n log n)。
  • 外层循环 O(n)，内层双指针遍历 O(n)，所以双指针部分总共是 O(n²)。
  • 总时间复杂度由更高的 O(n²) 决定。
• 空间复杂度：O(1) 或 O(n)（取决于排序算法）。
  • 我们只使用了几个额外的变量，如果不考虑存储结果的空间和排序所需的栈空间，空间复杂度是 O(1)。

总结

解决「三数之和」的关键三步：

1. 排序：为去重和使用双指针奠定基础。
2. 固定一个数：将三数之和转化为两数之和问题。
3. 双指针夹逼：在有序数组上高效地寻找另外两个数，并在过程中精心处理去重逻辑。

这道题的精髓在于理解并熟练运用排序后跳过重复元素的技巧来避免重复解，这是面试官非常看重的细节处理能力。希望你通过这个详细的讲解，能完全掌握这道经典的题目！