题解 | #三数之和#

三数之和

http://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<int>B;
        vector<vector<int> >A;
        if(num.size()<3)
            return A;
        //先给数组num从小到大排序
        sort(num.begin(), num.end());//排序
        for(int i=0;i<num.size()-2;i++){
            //每次都假设当前的数作为a
            if(i==0||num[i]!=num[i-1]){//保证这个三元组不重复的第一个条件
                int target=-num[i];
                //只要在i往后找两个数的和等于target即可
                int left=i+1;int right=num.size()-1;
                while(left<right){
                    if(num[left]+num[right]<target){
                        left++;
                    }
                    else if(num[left]+num[right]>target)
                        right--;
                    else{//此时num[left]+num[right]==target,但是要防止重复
                        if(left==i+1||num[left]!=num[left-1]){//不是重复的
                            B.push_back(num[i]);
                            B.push_back(num[left]);
                            B.push_back(num[right]);
                            A.push_back(B);
                            B.clear();
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return A;
    }
};
全部评论

相关推荐

07-22 11:53
门头沟学院 Java
终于有一个保底的offer了,但感觉是白菜价
北凝a:我想问问,提前批的offer 有问你啥时候到岗吗,如果你还想找其他的怎么办
点赞 评论 收藏
分享
昨天 12:30
湘潭大学 营销
点赞 评论 收藏
分享
陆续:不可思议 竟然没那就话 那就我来吧 :你是我在牛客见到的最美的女孩
点赞 评论 收藏
分享
斯卡蒂味的鱼汤:我认为就是逃课实习的学生技术才靠谱
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务