Leetcode：三数之和

题目链接：15. 三数之和 - 力扣（LeetCode）

普通版本（排序 + 双指针法）

分析：

1、我们可以通过三个循环嵌套找到符合题目要求的三元组组合

2、但由于题目要求中的三元组i、j、k并不要求连续，所以会出现下面的情况：

3、因此直接对原数组进行查找，可能会出现重复的情况，比如有abc的组合均满足条件但该组合有多种表现形式（a,c,b）（b,c,a）等重复的组合会导致我们的查找效率大大下降，因此我们应该先将数组进行排序，使得查找时三元组的顺序必然是从到大排序的，从而减少查找次数增加查找效率（假设排序前abc的组合满足要求，且a<=b<=c，那么排序后再进行查找时就不会出现（b,c,a）这种组合，最小的a一定是在最左边的）

sort(nums.begin(), nums.end());//排序

4、但是这样还不够，在循环时，相邻两次查找到的数组也不能相同否则也是重复，我们要跳转至下一个元素处，应该去查找组合（0，1，3）：

//实现上述防止重复查找的逻辑伪代码:
nums.sort()
for(first = 0 .. n-1)
{// 只有和上一次枚举的元素不相同，我们才会进行枚举if (first == 0 or nums[first] != nums[first-1]){for(second = first+1 .. n-1){if (second == first+1 or nums[second] != nums[second-1]){for(third = second+1 .. n-1){if(third == second+1 or nums[third] != nums[third-1]){// 判断是否有 a+b+c==0check(first, second, third)}}}}}
}                   

5、此时每次查找时一定满足，a<a‘、b<b'、c<c’（带'的都是新一次查找的），但最坏时间复杂度仍为O（N^3），我们尝试继续优化，我们会发现如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0，当第二重循环往后查找一个元素 b′时，由于 b′>b ，那么满足 a+b′+c′=0的 c′ 一定有 c′<c 即 c′ 在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针，从而得到下面的伪代码：

nums.sort()//排序
for (first = 0 .. n-1)    
{if(first == 0 or nums[first] != nums[first-1]){third = n-1;// 第三重循环对应的指针for(second = first+1 .. n-1){if(second == first+1 or nums[second] != nums[second-1]){// 向左移动指针，直到 a+b+c 不大于 0while(nums[first]+nums[second]+nums[third] > 0){third = third-1;}// 判断是否有 a+b+c==0check(first, second, third)}    }}
}

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());//排序vector<vector<int>> ans;// 枚举 afor (int first = 0; first < n; ++first) {// 需要和上一次枚举的数不相同if (first > 0 && nums[first] == nums[first - 1]) //first>0保证第一次循环可以正常进行，但是当第二次循环时如果两个a相同就，++first寻找下一个不相同的a{continue;}// c 对应的指针初始指向数组的最右端int third = n - 1;//int target = -nums[first];//获取a的负值，a+b+c = 0 => b + c = (-a)// 枚举 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚举的数不相同if (second > first + 1 && nums[second] == nums[second - 1])//跟前面一样，首先第一次循环要可以正常进行{continue;}// 需要保证 b 的指针在 c 的指针的左侧while(second < third && nums[first]+nums[second]+nums[third] > 0){--third;}// 如果指针重合，随着 b 后续的增加，就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if (second == third) {break;}if (nums[first]+nums[second]+nums[third] == 0) {ans.push_back({nums[first], nums[second], nums[third]});}}}return ans;}
};

时间复杂度：O（N^2）

空间复杂度：O（logN）（忽略存储答案的空间，额外的排序的空间复杂度为 O(log⁡N)）

~over~