15. 3Sum

Given an array of integers, are there elements a,b,c in 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]
]

思路1：在Two Sum的基础上再套一层，O(n^2)搞定

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        Arrays.sort(nums);

        for (int i=0;i<nums.length-2;i++){
            if (i==0||(i>0&&nums[i]!=nums[i-1])){
                int target = 0-nums[i];
                int left = i+1;
                int right = nums.length-1;
                while (left<right){
                    int sum = nums[left]+nums[right];
                    if (sum == target){
                        List<Integer> subList = new LinkedList<Integer>();
                        subList.add(nums[i]);
                        subList.add(nums[left]);
                        subList.add(nums[right]);
                        list.add(subList);
                        while(left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        while(left<right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }else if(sum < target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }

        return list;
    }
}

C++ code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> res;
        if (nums.size()<=2) return {};
        sort(nums.begin(), nums.end());

        for (int i=0; i<nums.size()-2;i++){
            if (i==0 || (i>0 && nums[i]!=nums[i-1])){
                int target = 0 - nums[i];
                int left = i+1;
                int right = nums.size()-1;
                while (left<right){
                    int sum = nums[left] + nums[right];
                    if (sum == target){
                        vector<int> subList;
                        subList.push_back(nums[i]);
                        subList.push_back(nums[left]);
                        subList.push_back(nums[right]);
                        res.push_back(subList);
                        while (left<right && nums[left]==nums[left+1]){
                            left++;
                        }
                        while (left<right && nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }else if(sum < target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        return res;
    }
};