三数之和 LeetCode15

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
 [-1, 0, 1],
 [-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

如果没有去重，列出所有情况，可以用以下作法（比较暴力）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int> a;
        vector<int>b;
        vector<int> paixuhou;
        vector<vector<int>> ex;
        for(int i=0;i<nums.size();i++){
            a.push_back(nums[i]);
            b.push_back(nums[i]);
        }
        //最关键的是 如何去重 思路1：hashmap+排序 总之需要排序，记录一个数字重复的次数
        for(int i=0;i<nums.size()-2;i++){
            for(int j=i+1;j<nums.size()-1;j++){
                for(int q=j+1;q<nums.size();q++){
                    if(i!=j&&i!=q&&j!=q){
                        if(nums[i]+a[j]+b[q]==0){
                            vector<int> tmp;
                            tmp.push_back(nums[i]);
                            tmp.push_back(a[j]);
                            tmp.push_back(b[q]);
                            ex.push_back(tmp);
                            //排序
                            
                        }
                    }
                }
            }
        }
        //重点 在于 输出 去重
        return ex;
        
    }
};

但是对于这个题而言，它的难点是去重。
需要会的知识点
STL vector排序（虽然可以自己写）
然后思路类似于快排 不过挺难写的
借鉴了别人的想法。
确定了一个数之后，另一个数确实是大数组包小数组 [1【2 2】3]

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
         vector<vector<int>> ex;
        if(nums.size()<3)
            return ex;
        //vector<vector<int>> ex;
        sort(nums.begin(), nums.end());
        //a定 另外两个数加和定 b定 c一定定 所以b不能重复。
        //a可以重复吗？a不可以 因为后一个重复的a它的情况一定包括在前一个中
        for(int i=0;i<nums.size()-2;i++){
            int b=i+1;
            int c=nums.size()-1;
           if(i>0 &&nums[i]==nums[i-1])
               continue;
            while(b<c){
                int sums=nums[i]+nums[b]+nums[c];
                if(sums==0){
                    vector<int> tmp;
                    tmp.push_back(nums[i]);
                    tmp.push_back(nums[b]);
                    tmp.push_back(nums[c]);
                    ex.push_back(tmp);
                    b+=1;
                    c-=1;
                    while(b<c && nums[b]==nums[b-1])
                        b+=1;
                    while(b<c && nums[c]==nums[c+1])
                        c-=1;
                }else if(sums>0){//c过大
                    c-=1;
                    
                }else if(sums<0){//b过小
                    b+=1;
                }
                

            }
            

        }

        return ex;
        
    }
};