[优选算法专题一双指针——三数之和]

题目链接

LeetCode三数之和

题目描述

题目解析

一、问题核心与解题思路

问题：给定整数数组 nums，返回所有不重复的三元组 [a, b, c]，满足 a + b + c = 0 且 a、b、c 对应数组中不同索引的元素。

核心难点：

1. 找到所有满足条件的三元组；
2. 避免结果中出现重复的三元组。

解题思路：采用 「排序 + 双指针」 组合策略，具体步骤如下：

1. 排序数组：为双指针查找和去重提供基础；
2. 固定第一个元素：通过外层循环遍历每个可能的第一个元素 a = nums[i]；
3. 双指针找剩余两个元素：在内层用左右指针（left = i+1，right = n-1）寻找 b 和 c，使得 a + b + c = 0；
4. 去重处理：对三个指针跳过重复元素，避免生成重复三元组。

注意：

在去重的操作中可以使用set去重，但是我们这里推荐，因set 去重虽然能实现功能，但会显著降低效率，且编写代码的复杂程度也会提升，违背了「三数之和」的最优解法思路。因此，更推荐通过排序 + 跳过重复元素的方式去重，既高效又简洁。

这里举例一个已经排过序的新数组：

我们先固定第一个数：

这里就转化成了和为sum的问题，这里的s就是这个固定的数的相反数。也就是：

所以这里解决步骤：

1. 先对整个数组排序
2. 固定一个数 a（这里有个小优化，后续介绍）
3. 在该数后面的区间内，利用双指针算法快速找到两个数的和为 -a 的即可。

注意：这里只是找到了符合条件的情况，并没有去重。

接下来就是处理细节问题了，也就是去重和确保所有符合条件的情况不落下。

二、关键逻辑与优化解析

1. 排序的作用
   排序后：

   • 相同元素相邻，便于跳过重复值（去重核心）；
   • 数组有序，可通过双指针高效调整三数之和的大小（左移减小、右移增大）。

2. 外层循环的优化

   • if (nums[i] > 0) break：
     排序后数组递增，若 nums[i] > 0，则 nums[left] 和 nums[right] 均 ≥ nums[i]，三数之和必 > 0，无需继续循环。
   • if (i + 2 < n && nums[i] + nums[i+1] + nums[i+2] > 0) break：
     对于当前 i，最小的可能组合是 nums[i] + nums[i+1] + nums[i+2]（后两个是最小的剩余元素）。若此和 > 0，说明当前 i 及更大的 i 都无有效组合，直接退出。

3. 双指针的移动逻辑

   • 当 sum == 0：找到有效三元组，加入结果后，需同时移动左右指针并跳过重复值（否则会生成相同三元组）；
   • 当 sum < 0：和太小，左指针右移（增大 nums[left]）；
   • 当 sum > 0：和太大，右指针左移（减小 nums[right]）。

4. 去重的关键细节

   三、完整代码

   

   • 对 i 去重：避免因固定元素重复导致的三元组重复（如 [-1, -1, 2] 与 [-1, -1, 2]）；
   • 对 left 和 right 去重：找到一组解后，需跳过相邻的相同元素（如 [-2, 0, 0, 2, 2] 中，找到 [-2, 0, 2] 后需跳过重复的 0 和 2）。

四、常见错误点

1. 越界问题：
   需确保 i + 2 < n 再判断 nums[i] + nums[i+1] + nums[i+2]，否则可能访问无效索引。

2. 去重时机错误：
   必须在找到有效三元组后再去重（如 sum == 0 时），不能提前去重，否则可能漏掉合法解。

3. 指针移动遗漏：
   找到有效解后，需同时移动 left 和 right（而非只移动一个），否则可能陷入死循环。

五、复杂度分析

• 时间复杂度：

  • 排序：O(n log n)；
  • 外层循环 O(n) + 内层双指针 O(n)，整体为 O(n²)；
    总时间复杂度：O(n²)（排序可忽略）。

• 空间复杂度：

  • 除结果存储外，仅使用常数级额外空间（指针、临时变量），故为 O(1)（若考虑排序的栈空间，最坏为 O(log n)）。