Leetcode数组Medium | 15. 三数之和

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答：

//之前做过两个数之和等于某个数的题目，其实这题也差不多，三数之和等于0，那么我们只要让另外两个数之和等于第三个数的相反数即可，不过这里要注意会存在重复，所以要去重
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //思路：
        vector<vector<int> > ret;  //  新建二维数组
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            int t1=i+1,t2=nums.size()-1;
            if(i&&nums[i]==nums[i-1])  //  若原数组中存在重复元素，即i元素等于上一位元素，则下一轮循环
                continue;
            while(t1<t2){
                if(nums[t1]+nums[t2]==-nums[i]){
                    vector<int> v; //  新建数组，每次循环需重置
                    v.push_back(nums[i]);
                    v.push_back(nums[t1]);
                    v.push_back(nums[t2]);
                    ret.push_back(v);
                    ++t1;  
                    --t2;
                }  //  三个数的和为0，即其中两个数的和等于另一个的相反数。循环从头到尾
                else if(nums[t1]+nums[t2]<-nums[i])
                    ++t1;
                else
                    t2--;
            }
        }
        auto pos = unique(ret.begin(),ret.end());  //  auto 自动推断类型；unique将重复的放在末位，返回其位置
        ret.erase(pos,ret.end());  //  删除末尾重复的元素
        return ret;
    }
};