15. 三数之和

题目描述

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

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

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

解题思路

1.枚举法

刚刚看到这道题很容易想到使用枚举的方法，将每三个元素进行枚举，查看是否和为0，但是这样枚举有一个非常重要的问题就是：怎么去除重复的三元组

vector<vector<int>> threeSum(vector<int>& nums) {
        int i=0,j=0,k=0;
        vector<vector<int>> ans;
        vector<int> temp;
        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){
                        temp.push_back(nums[i]);//把满足条件的元素放入数组中
                        temp.push_back(nums[j]);
                        temp.push_back(nums[k]);
                        ans.push_back(temp);
                        temp.clear();
                    }
                }
            }
        }
    return ans;
    }

输出结果：

输入
[-1,0,1,2,-1,-4]
输出
[[-1,0,1],[-1,2,-1],[0,1,-1]]
预期结果
[[-1,-1,2],[-1,0,1]]

可以看到上面的输出结果中，多出了重复的三元组。

2. 解决思路(1)

首先怎么解决重复三元组去除的问题？

1. 首先可以对原数组进行排序
2. 这时候如果相邻的两个元素有重复的时候，那么这时候可能会重复，把这种情况排除

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

for(int m=0;m<ans.size();m++){//如果有重复就就不加入数组
   if(ans[m]==temp)ap=0;
}
if(ap==1){
  ans.push_back(temp);
}
ap=1;

这个思路的最大问题就是超时问题，当数组长度很长时，运算结果会出现超时。下面需要对其进行优化。

3. 最终方案：排序+双指针

能不能把上面的三重循环化简为双循环呢？这里需要使用双指针方法：

可以发现，如果我们固定了前两重循环枚举到的元素a和b，那么只有唯一的c满足 a+b+c=0。当第二重循环往后枚举一个元素 b’时，由于b’>b，那么满足a+b’+c’=0的c’一定小于c；所以第三个指针不用修改为原始值，直接只需要在原来的基础上减少就可以，这样枚举某一个a的时候，只需要循环一遍数组就可以。

这里使用的去除重复的方法也不同：原理是如果不是初始位置的值，有相邻值相同的情况出现则需要直接略过[1]

vector<vector<int>> threeSum(vector<int>& nums) {
        int i=0,j=0,k;
        vector<vector<int>> ans;
        vector<int> temp;
        sort(nums.begin(),nums.end());
        for(i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1])continue;//[1]
            k=nums.size()-1;//j从前往后，k从后往前
            for(j=i+1;j<nums.size();j++){
            if(j>i+1&&nums[j]==nums[j-1])continue;//[1]
                while(nums[i]+nums[j]+nums[k]>0&&j<k)    
                    k--;
                if(nums[i]+nums[j]+nums[k]==0&&j<k){
                    temp.push_back(nums[i]);
                    temp.push_back(nums[j]);
                    temp.push_back(nums[k]);
                    ans.push_back(temp);
                    temp.clear();
                }

            }
        }
        return ans;
    }