hot100 15 三数之和

题目给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为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 。提示3 nums.length 3000-105 nums[i] 105可以这样理解三数之和 排序后固定一个数再用双指针找另外两个数。为什么不能直接三重循环最容易想到的是for (int i 0; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { if (nums[i] nums[j] nums[k] 0) { // 记录答案 } } } }问题有两个第一时间复杂度是O(n^3)题目中nums.length 30003000^3太大会超时。第二结果会重复。例如nums [-1, 0, 1, 2, -1, -4]里面有两个-1所以可能多次得到[-1, 0, 1]但题目要求答案中不能有重复三元组。为什么要排序排序后的数组有两个好处。原数组[-1, 0, 1, 2, -1, -4]排序后[-4, -1, -1, 0, 1, 2]好处一方便去重。比如两个-1是挨在一起的[-4, -1, -1, 0, 1, 2] ↑ ↑所以我们可以判断if (i 0 nums[i] nums[i - 1]) continue;意思是如果当前这个数和前一个数一样说明之前已经以这个数作为第一个数找过答案了这次直接跳过。好处二可以使用双指针。因为排序后数组是有序的小 ---------------------- 大当三数之和太小时可以让左指针右移让总和变大。当三数之和太大时可以让右指针左移让总和变小。核心思路固定一个数寻找另外两个数假设排序后[-4, -1, -1, 0, 1, 2]我们固定第一个数a。比如a -1那么问题就变成找两个数 b 和 c使得 a b c 0也就是b c -a如果a -1那么b c 1这就变成了一个“两数之和”问题。区别是这里数组已经排序所以可以用双指针不需要哈希表。4. 双指针怎么移动固定i作为第一个数int left i 1; int right n - 1;然后计算sum nums[i] nums[left] nums[right];分三种情况情况 1sum 0说明找到一个答案ans.push_back({nums[i], nums[left], nums[right]});然后left; right--;继续找下一个答案。情况 2sum 0说明当前和太小了。因为数组已经排序想让和变大就要让left右移left;例如[-4, -1, -1, 0, 1, 2] i L R sum -4 (-1) 2 -3太小了所以left往右走找更大的数。情况 3sum 0说明当前和太大了。想让和变小就要让right左移right--;例如[-4, -1, -1, 0, 1, 2] i L R sum -1 0 2 1太大了所以right往左走找更小的数。用示例完整走一遍输入[-1, 0, 1, 2, -1, -4]排序[-4, -1, -1, 0, 1, 2]第一轮固定 nums[i] -4i 0 nums[i] -4 left 1 right 5[-4, -1, -1, 0, 1, 2] i L R计算sum -4 (-1) 2 -3太小left。继续[-4, -1, -1, 0, 1, 2] i L Rsum -4 (-1) 2 -3还是太小left。继续[-4, -1, -1, 0, 1, 2] i L Rsum -4 0 2 -2还是太小left。继续[-4, -1, -1, 0, 1, 2] i L Rsum -4 1 2 -1还是太小left。此时left right结束。这一轮没有答案。第二轮固定 nums[i] -1[-4, -1, -1, 0, 1, 2] i L R计算sum -1 (-1) 2 0找到答案[-1, -1, 2]然后left right--变成[-4, -1, -1, 0, 1, 2] i L R计算sum -1 0 1 0找到答案[-1, 0, 1]继续移动left right--此时left right结束。第三轮固定 nums[i] -1下标变成i 2但是nums[2] nums[1]也就是当前的-1和上一个-1重复。所以跳过。因为上一轮已经以-1作为第一个数找过答案了。最终答案[[-1, -1, 2], [-1, 0, 1]]完整代码std::vectorstd::vectorint threeSum(std::vectorint nums) { std::vectorstd::vectorint result {}; // 先对数组进行排序 std::sort(nums.begin(),nums.end()); int L 1; int R nums.size() - 1; for (int i 0; i nums.size();i){ if(nums[i] 0){ break; } if (i 0 nums[i] nums[i-1]) // 跳过重复的第一个数 { continue; } L i 1; R nums.size() - 1; // 在这里赋值是为了防止 nums[i] 和 nums[i-1] 相等时L 和 R 没有被重置 while (LR) { int sum 0; sum nums[i] nums[L] nums[R]; if(sum 0){ result.push_back({nums[i],nums[L],nums[R]}); // 跳过重复的第二个数 while (L R nums[L] nums[L 1]) { L; } // 跳过重复的第三个数 while (L R nums[R] nums[R - 1]) { R--; } // 或者两个while循环合并 // while (L R nums[L] nums[L 1] nums[R] nums[R - 1]) { // L; R--; // } 会增加常数级别的计算性能会稍微下降 L; R--; } else if (sum 0){ L; } else{ R--; } } // Li2; // Rnums.size() - 1; } return result; }这里精髓在于三次去重第一次去重if (i 0 nums[i] nums[i - 1]) { continue; }这次去重还是很好理解的。如果 定 后一个数和前一个数一样则必定是重复的。第二次去重这段代码while (L R nums[L] nums[L 1]) { L; }意思是当前nums[L]已经参与组成过一个答案了如果右边还有相同的nums[L]继续用它一定会产生重复三元组所以直接跳过。例如[-2, 0, 0, 0, 2] L当前L指向第一个0。如果已经用[-2, 0, 2]作为答案那么后面的0再和-2、2组合还是[-2, 0, 2]所以要跳过所有重复的0。第三次去重跳过重复的 R这段代码while (L R nums[R] nums[R - 1]) { R--; }意思是当前nums[R]已经参与组成过一个答案了如果左边还有相同的nums[R]继续用它一定会产生重复三元组所以直接跳过。例如[-2, 0, 2, 2, 2] R当前R指向最后一个2。已经得到[-2, 0, 2]那么前面的那些2再参与组合也还是[-2, 0, 2]所以要跳过所有重复的2。