首页 > 代码库 > 3Sum

3Sum

Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:[  [-1, 0, 1],  [-1, -1, 2]]


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

 

3Sum