美文网首页
15.三数之和

15.三数之和

作者: 薄荷糖的味道_fb40 | 来源:发表于2019-04-17 10:39 被阅读0次

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

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

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

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

思路:

1.三重循环遍历,毫无疑问地超时了
2.先排序,两重循环加上二分查找,也超时了
3.先排序,遍历nums数组小于等于0的数作为第一个数sum,设置头尾指针,看头尾指针所指元素相加是否为-sum,如果相等,若不重复则记录,尾指针--头指针++,如果大于-sum,尾指针--,如果小于-sum,头指针++。
关键就是看有没有重复的部分了,就是要看结果的第一个元素和第二个元素是否相等,对于结果的第一个元素,排序后的数组只要关心当前元素的sum值是否等于上一项元素的sum值就好了,同理,对于第二个元素,排序后的数组只要关心当前值是否与上一项值相等即可,实现代码如下。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> temp;
        if(nums.size()<3)
        {
            return res;
        }
        sort(nums.begin(),nums.end());
        int sum=INT_MIN;
        for(int i=0;i<nums.size()-2;i++)
        {
            if(nums[i]<=0)
            {
                temp.push_back(nums[i]);
                if(sum==0-nums[i])
                {
                    temp.pop_back();
                    continue;
                }
                sum=0-nums[i];
                int front=i+1;
                int back=nums.size()-1;
                int second=nums[front]-1;
                while(front<back)
                {
                    if(nums[front]+nums[back]==sum)
                    {
                        if(second!=nums[front])
                        {
                            second=nums[front];
                            temp.push_back(second);
                            temp.push_back(nums[back]);
                            res.push_back(temp);
                            temp.pop_back();
                            temp.pop_back();
                        }
                        front++;
                        back--;
                    }
                    else if(nums[front]+nums[back]>sum)
                    {
                        back--;
                    }
                    else
                    {
                        front++;
                    }
                }
                temp.pop_back();
            }
        }
        return res;
    }
};

相关文章

网友评论

      本文标题:15.三数之和

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