每日一道 LeetCode (52)：三数之和
共 823字，需浏览 2分钟
·
2020-10-14 22:37
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
每日一道 LeetCode 前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：三数之和
难度：「中等」
题目来源：https://leetcode-cn.com/problems/3sum/
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解题思路
之前一段时间都在写 JVM 和 Tomcat 的一系列相关的文章，刷力扣题就给空下了，今天开始接着捡起来做题。
首先这道题我第一个反应是套三个循环，肯定做得出来，时间复杂度是 O(n^3) ，放在力扣里面，按照一贯的尿性结果肯定是超时，这个方案我现在都已经懒得写了（对，我现在就是这么飘），除了锻炼下写代码的能力，对于算法好像没啥提升。
其他的方案又想不出来，没办法，只能去翻答案。
答案上的思路就很有意思了，第一件事儿就是先给数组排序，把这个数组变成一个有序数组。
三个数加起来结果要是 0 ，会有一种特殊情况就是 0 + 0 + 0 = 0 。
刨除掉上面这种情况，那么肯定第一位是负数，后面第二位只能比第一位大，第三位要比第二位大（这不是显而易见嘛）。
套上前面的特殊情况，那么会有一个确定的关系 a <= b <= c 。
这个问题解到这里，还是没有跳脱出来三重循环，那么时间复杂度依然还是 O(n^3) ，这肯定不行，还需要继续优化。
目标放在把时间复杂度降低到 O(n^2) 上，那么就是两重循环要搞定所有的事儿，最外层的循环也就是找 a 的那个循环，这个肯定是无法避免的，能玩的滑头也就只剩下第二重循环了，在找 b 和 c 的过程，想办法找到内在的联系，在一次循环中，直接把 b 和 c 全都找出来。
如果我们固定了 a 和 b ，那么只会有一个唯一的 c 来满足 a + b + c = 0 。当第二重循环往后再循环一个 b1 的时候，这时如果存在 a + b1 + c1 = 0 ，那么这个 c1 一定要比之前的 c 来的要小。
这样我们可以在第二重循环里面考虑一个双指针的方案，一个数组从小到大排列，取 b 的时候我们从小到大取，取 c 的时候我们从大到小来取，这时，我们取 b 和 c 其实是并列在第二重里面的，这样我们强行把三重循环降成了两重循环。
这里的 b 和 c 可以抽象成两个指针，左指针和右指针，左指针每像右移动一位，右指针向左有可能移动 n 位，这和数组的元素有关，最差情况下会达到移动 n 次，因此，时间复杂度也是 O(n) ，第一重循环还有一个 O(n) ，所以整体的时间复杂度会达到 O(n^2) 。
代码：
public List> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List> ans = new ArrayList<>();
// 最外层循环，迭代 a
for (int a = 0; a < n; ++a) {
// 由于元素不能重复，遇到相同的直接下次循环
if (a > 0 && nums[a] == nums[a - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int c = n - 1;
int target = -nums[a];
// 迭代 b
for (int b = a + 1; b < n; ++b) {
// 一样先判断是否和上次迭代的元素是否相同
if (b > a + 1 && nums[b] == nums[b - 1]) {
continue;
}
// b 的位置在 c 的左侧
while (b < c && nums[b] + nums[c] > target) {
--c;
}
// 如果出现了指针重合，就可以退出循环了，说明没找到对应的 c
if (b == c) {
break;
}
// 如果出现了 b 和 c 加起来等于 -a ，说明我们找到的最后的结果
if (nums[b] + nums[c] == target) {
List list = new ArrayList<>();
list.add(nums[a]);
list.add(nums[b]);
list.add(nums[c]);
ans.add(list);
}
}
}
return ans;
}
❝不知道各位还记不记得之前两数之和的解法，当我们确定了 a 和 b 以后，最终寻找 c 的时候还可以把整个数组放在一个哈希表中，通过哈希表的特性来判断当前 c 是否存在，如果不存在，则进入下一次循环。
❞
