美文网首页
Leetcode数组Medium | 15. 三数之和

Leetcode数组Medium | 15. 三数之和

作者: Ivan_Lan | 来源:发表于2018-11-30 19:40 被阅读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;
        }
    };
    

    相关文章

      网友评论

          本文标题:Leetcode数组Medium | 15. 三数之和

          本文链接:https://www.haomeiwen.com/subject/uyhkcqtx.html