【数组】【双指针】三数之和

打算冲一把算法类比赛，之前一直对算法提不起兴趣，也有我自己对它的抵触，本身算法也比较菜。
但现在打算勤勤恳恳刷题，踏踏实实总结，冲！

数组——双指针

三数之和

该题力扣网址

错误做法

三重循环框架，最浅显的思路，复杂度是N^3，没有任何优化。

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

结果就是超时！

也是我第一次刷力扣吧，确实能够提升思路

琢磨了点，但是因为太菜，好几个月没碰算法，没有什么有效的思路，一直脱离不开三层循环框架，于是看了题解，再次感叹题解做法秒！

再次提交做法

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int i,j,k;
        vector<vector<int>> ans;
        // 先排序
        sort(nums.begin(),nums.end());
        for(i=0;i<nums.size();i++){
            //先确定第一个数
            //这个数和上一数不能大小相等
            if(i!=0 && nums[i]==nums[i-1]){
                continue;
            }
            for(j=i+1;j<nums.size();j++){
                if(j!=i+1 && nums[j]==nums[j-1]){
                    continue;
                }

                k = nums.size()-1;
                while(k>j && nums[i]+nums[j]+nums[k]>0){
                    k--;
                }
                if(k==j){
                    break;
                }
                if(nums[i]+nums[j]+nums[k]==0){
                    ans.push_back({nums[i], nums[j], nums[k]});
                }
                
            }

        }
        return ans;
    }
};

以上是我看了题解之后自以为懂了，但是提交之后仍然是超时！！

然后我又返回去看题解，不得不说还是上次看题解没有真正理解！o(╥﹏╥)o

算法思路

算法思路是这样滴
把三数之和转换成两数之和，也就是在每次循环第一个数时，就相当于把这个数确定下来了，这个时候，再分析剩下两个数的关系，如何让它们仨相加等于0就可以了。
与此同时，还需要注意几个点：

1. i!=j and j!=k and i!=k
   三个数的下标不同，这个简单，循环的时候让第二个数的下标等于第一个数坐标+1就可
   （例如：j=i+1）

2. 数组里有重复的数，但是输出要求不能有重复的数组
   首先给原数组排序，让相等的数挨着，才能用nums[j]!=nums[j-1]确保每次选的数之前没有选过。但是，例如：nums[j-1]注意不能和nums[i]相等，因此这个判断条件需要加上当j!=i+1的时候

3. 时间复杂度的问题
   第一个数和第二个数都是用嵌套循环确定的，从左往右依次选取，时间复杂度已经是N^2了
   如果第三个数再嵌套实现，那还是N^3

   在每次对第一个数已经确定的情况下（假设第一个数为num1），对第二个数进行循环，因为每次都是从左往右，也就是从小到大选，那对第三个数来说：

   1. 如果从左往右选（从小到大），由于第二个数也是从小到大选，假设对于第二个数的某个值来说，存在num3满足num1+num2+num3=0。那么当这一轮结束，j+1，开始找num2’对应的num3’，使满足num1+num2’+num3’=0，此时，num2’肯定＞num2，那说明num3’肯定要＜num3，但是第三轮的循环，k初始为j+1，也就是从左往右选 ，那么，如果在最差的情况下，num3在n-1的下标处，相当于每次第二轮循环结束之后，k都要从j+1重新从左往右选取，这样下来时间复杂度就还是N^3，没有任何提升，还是AC不了。
   2. 如果从右往左选（从大到小），接着1.的开始找num2’对应的num3’，使满足num1+num2’+num3’=0说起，这时k的初始化为n-1，num2’>num2，需要num3’<num3，这样k就不用再重新初始化了，直接在上一个num3的下标位置再往左走就好，这样k的初始化应该在第二轮循环之前，第一轮循环之后，时间复杂度也就变成了N^2。即，k不是每次在第二个数循环里都需要初始化为k=n-1,（我上一个超时的代码就犯了这个错误 ）

AC代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int i,j,k;
        vector<vector<int>> ans;
        // 先排序
        sort(nums.begin(),nums.end());
        for(i=0;i<nums.size();i++){
            //先确定第一个数
            //这个数和上一数不能大小相等
            if(i!=0 && nums[i]==nums[i-1]){
                continue;
            }
            k = nums.size()-1;
            for(j=i+1;j<nums.size();j++){
                if(j!=i+1 && nums[j]==nums[j-1]){
                    continue;
                }

                while(k>j && nums[i]+nums[j]+nums[k]>0){
                    k--;
                }
                if(k==j){
                    break;
                }
                if(nums[i]+nums[j]+nums[k]==0){
                    ans.push_back({nums[i], nums[j], nums[k]});
                }
                
            }

        }
        return ans;
    }
};