3Sum

medium 原题链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/submissions/

3Sum

原题链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/submissions/

描述

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

Notice that the solution set must not contain duplicate triplets.

例子

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

约束条件

• 0 <= nums.length <= 3000

• -105 <= nums[i] <= 105

解法一

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());
        int len = nums.size();
        for(int i=0; i< len-2; i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]>0) break;
            if(nums[i]+nums[len-2]+nums[len-1]<0) continue;
            int j=i+1, k=len-1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum > 0) --k;
                else if(sum < 0) ++j;
                else{
                    res.push_back({nums[i],nums[j],nums[k]});
                    do{++j;}while(nums[j] == nums[j-1] && j<k);
                    do{--k;}while(nums[k] == nums[k+1] && j<k);
                }
            }
                
        }
        return res;
        
    }
};

解法二