15. 三数之和

15. 三数之和

vector<vector<int>> threeSum(vector<int>& nums){
	vector<vector<int>> result;
	sort(nums.begin(),nums.end());
	//找出a+b+c=0
	//a=nums[i],b=nums[left],c=nums[right]
    for(int i = 0 ;i<nums.size();i++){
        //排序之后如果第一个元素已经大于0，那么无论如何都不可能组成三元组了
        if(nums[i]>0){
            return result;
        }
        //i去重
        if(i>0&&nums[i]==nums[i-1]){
            continue;
        }
        int left=i+1;
        int right=nums.size()-1;
        while(right>left){
            if(nums[i]+nums[left]+nums[right]>0) right--;
            else if(nums[i]+nums[left]+nums[right]<0) left++;
            else{
                result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                while(right>left&&nums[right]==nums[right-1]) right--;
                while(right>left&&nums[left]==nums[left+1]) left++;
                right--;
                left++;
            }
        }
    }
    return result;
}