LC15. 三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。

题目解析

题目在说什么

给你一堆数字，比如 [-1, 0, 1, 2, -1, -4]。你要从里面挑出三个数，让它们的和等于 0。而且，如果找到好几组，里面不能有重复的（比如 [-1, 0, 1] 出现了两次，只能算一次）。最后把所有这样的三个数组合都列出来。

听起来像“找朋友”：三个人加起来刚好是 0 块，而且不能找一模一样的三人组两次。

思路是怎么来的

如果暴力解决

最直接的想法：把数组里所有三个数的组合都试一遍。比如数组有 6 个数，那就试 C(6,3)=20 种组合，每种算一下和是不是 0。这种方法叫“三重循环”，时间复杂度是 O(n³)。当数组有几百个数时，电脑会算到崩溃。

怎么优化？

我们想：能不能少试一些组合？比如先让数组排好序（从小到大），这样就能利用“大小关系”来快速判断。

• 如果三个数中最小的那个已经大于 0 了，那后面更大的数加起来肯定大于 0，就不用再试了。
• 如果三个数的和小于 0，说明需要更大的数，那就把左边的指针往右移；如果和大于 0，说明需要更小的数，就把右边的指针往左移。

这就是“双指针”技巧：一个指针从左边开始，一个从右边开始，像两个人面对面走，边走边调整，直到碰头。

生活比喻

想象你在一条街上，街上的房子按门牌号从小到大排列（排序）。你站在某个位置 i，然后让两个朋友分别从 i 的右边（left）和街尾（right）同时往中间走。你们三个人要凑出 0 块钱。如果三个人的钱加起来太少（<0），就让左边那个朋友往前走一步（拿更多钱）；如果太多（>0），就让右边那个朋友往回走一步（拿更少钱）。这样很快就能找到合适的组合，而不用试遍所有人。

代码逐步拆解

我们来看参考代码，一行一行解释。

List<List<Integer>> ans = new ArrayList();

• 创建一个“大袋子”，用来装所有找到的“三个数组合”。每个组合是一个小列表，比如 [-1, 0, 1]。

int len = nums.length;
if(nums == null || len < 3) return ans;

• 如果数组是空的，或者数字少于 3 个，那肯定找不到三个数，直接返回空袋子。

Arrays.sort(nums);

• 把数组从小到大排序。比如 [-1, 0, 1, 2, -1, -4] 变成 [-4, -1, -1, 0, 1, 2]。排序是后面所有操作的基础。

for (int i = 0; i < len ; i++) {

• 外层循环：固定第一个数 nums[i]。i 从 0 开始，一个一个往后移。

if(nums[i] > 0) break;

• 如果 nums[i] 已经大于 0 了，那它后面（右边）的数都更大，三个正数加起来肯定大于 0，所以直接结束整个循环。这叫“剪枝”，省时间。

if(i > 0 && nums[i] == nums[i-1]) continue;

• 去重：如果当前这个数和前一个数一样，那再找一遍就会得到重复的三元组。比如数组中有两个 -1，第一个 -1 已经找过所有组合了，第二个 -1 再找就是重复劳动，直接跳过。

int left = i + 1;
int right = len - 1;

• 初始化两个指针：left 指向 i 的下一个位置，right 指向数组最后一个位置。它们会在 while 循环里向中间移动。

while(left < right){
    int sum = nums[i] + nums[left] + nums[right];

• 计算三个数的和。

if(sum == 0){
    ans.add(Arrays.asList(nums[i],nums[left],nums[right]));

• 如果和正好是 0，就把这三个数装进袋子。

while( left < right && nums[left] == nums[left + 1]) left++;

• 去重：如果 left 右边的数和 left 相同，那 left 再往右移一步就会得到重复的组合。比如 [-2, 0, 0, 2, 2]，当 left 指向第一个 0 时，如果 right 指向最后一个 2，和为 0。但如果 left 移到第二个 0，right 移到第一个 2，和还是 0，但组合相同。所以我们要跳过所有重复的 left。

while( left < right && nums[right] == nums[right - 1]) right--;

• 同理，跳过重复的 right。

left++;