Leetcode15. 三数之和(HOT100)

链接

一般这种三数之和，四数之和都使用双指针，复杂度最优，次一级可使用哈希表。前者要求有序，后者空间上有花费。

题目：

题目要求答案中不能出现重复vector，比如{-1 1 0}和{-1 0 1}；

这两个在固定住i 指向0位置，然后在后续子数组中查找合适的j 和k 时，会出现重复，所以我们对数组排序，通过if语句解决重复问题。

我们要找nums[i]+num[j]+nums[k]==0，乍一看，需要三个指针，三种循环来判断，但这显然是不合适的，于是我们固定住i（也就是让i从开头遍历到结尾即可），然后让j 从i 后面开始，k从最后一个元素开始往中间遍历。

如果刚开始（也就是图中这个位置），三个相加都小于0，那么就不存在答案，因为我们的数组是有序的，k越往做，越小了。

所以，我们只需要找三个相加大于等于0的，这样越往前越有可能找到==0的情况。

为什么要一直往前呢？万一出现下图这样，k指向的值刚好就可以和nums[i] nums[j]相加为0，为何还要往前？

因为我们怕重复，{-2 0 2}，{-2 0 2}，{-2 0 2}，{-2 0 2}...........这不符合题目要求，所以我们尽量往左走，只留一个就行了。

另外，代码中其实还有可以优化的地方：

也就是这两点，因为排序后，并不能去重，所以会出现：

i指向这两个位置，找到的答案还是会重复，所以我们在i 至少找过一次（也就是i！=0即 i）时，且nums[i]==nums[i-1]时，continue住，不要往下循环了，别找了，答案如果有都是一样的，没必要循环了。

还有j 的情况也是如此：j>i+1也就是j 在当前i 这个位置至少已经找过一次了，如果j 往后挪了还是相等，那也不用找了。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i++) {if (i && nums[i] == nums[i - 1]) // if (i + 1 < nums.size() &&// nums[i] == nums[i + 1])continue;for (int j = i + 1, k = nums.size() - 1; j < k; j++) {if (j > i + 1 &&nums[j] == nums[j - 1]) // if (j + 1 < nums.size() &&// nums[j] == nums[j + 1])continue;while (k - 1 > j && nums[j] + nums[k - 1] + nums[i] >= 0)--k;if (nums[i] + nums[j] + nums[k] == 0) {res.push_back({nums[i], nums[j], nums[k]});}}}return res;}
};