15. 3 SUM

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

Follow up: 如果不sort能怎么做

Thoughts:

a + b + c =0 <=> a + b = -c

Traverse each element : a target of two sum. Search direction should be consistent with the direction of traverse order(avoid duplicates).

[code 1: using map]: O(n^2) + Extra Space (HashMap/ unordered_map) : https://leetcode.com/problems/3sum/discuss/163934/Efficient-Java-Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) map.put(nums[i], i); // val , last index

        for(int i = 0 ; i < nums.length - 2; i++){
            for(int j = i + 1; j < nums.length -1; j++){
                int target = 0 - nums[i] - nums[j];

                if (map.containsKey(target) && map.get(target) > j){
                    res.add(Arrays.asList(nums[i], nums[j], target));
                    j = map.get(nums[j]); // Taking the last index of j to remove duplicate 
                }
            }
            i = map.get(nums[i]); // Taking the last index of i to remove duplicate
        }

        return res;
    }
}

FollowUp: without Sort https://leetcode.com/problems/3sum/discuss/110507/Golang-~n2+n-worst-case-no-sort-no-deduplication-O(n2)-beats-50

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length == 0) return new ArrayList<>();
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>(); // 1
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0 ; i < n; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        // cross product
        for(int i : map.keySet()){
            for(int j: map.keySet()){
                if(i > j || (i == j && map.get(i) == 1)) // imposing j>= i
                    continue;

                int k = -i - j;
                if(map.containsKey(k)){
                    if(j > k) continue; // imposing k >= j order
                    int size = map.get(k);
                    if(((k == j)&& size == 1) ||            // since k >= j >= i 
                       ((k == i && i == j) && size == 2)) // deduplication 
                        continue;

                    res.add(Arrays.asList(i,j,k));
                }
            }
        }

        return res;
    }
}

Python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # time O(n^2), space O(1)
        if not nums: return []

        n, m = len(nums), collections.defaultdict(int) # {x:nums.count(x) for x in nums} #dict(collections.Counter(nums)) 
        for num in nums: m[num]+=1


        return [[i, j, -i-j] for i in m.keys() 
            for j in m.keys() if (j > i or (i == j and m[i] > 1)) 
            and ((-i -j) in m )
            and ((-i-j)>= j)
            and (m[(-i-j)] > 2 or m[(-i-j)] == 1 and (-i-j)!=j or m[(-i-j)] == 2 and ((-i-j)!=i or (-i-j)!=j))]

[code 2: two pointer]: O(n^2) without extra space (ordered_map)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList();
        int n = nums.length;
        for(int i = 0; i < n - 2;  i++){
            if(i == 0 || nums[i] != nums[i-1]){
                int j = i + 1, k = n - 1;
                while(j < k){
                    if(nums[i] + nums[j] + nums[k] == 0){
                        res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        // deduplication
                        while(j < k && nums[j] == nums[j + 1]) j ++;
                        while(j < k && nums[k] == nums[k - 1]) k --;
                        j++; k--;
                    }
                    else if(nums[i] + nums[j] + nums[k] < 0) j++;
                    else k --;
                }
            }
        }

        return res;
    }
}

Variation: Expand sum to be 0 as in general case

class Solution {
    vector<vector<int>>answer;
public:
    vector<vector<int>> threeSum(vector<int>& nums, int target) {
        int len = nums.size();
        if (len < 3) return answer;

        // sort the vector
        sort(nums.begin(), nums.end());

        for(int i = 0; i < len; i++){

            int left = i + 1, right = len - 1, twoSumTarget = target - nums[i]; // THE ONLY DIFFERENCE!

            // treat as two sum using two pointers
            while(left < right){
            // speed up two sum runtime by removing two sum search for duplicated target value 
            // while(i > 0 && nums[i] == nums[i-1]) i++; 
            // alternatively, you can write :
            if(i>0 && nums[i] == nums[i-1]) continue;
            //at the beginning of the for loop


                int sum = nums[left] + nums[right];
                if( sum == twoSumTarget ){
                    answer.push_back({nums[i], nums[left],nums[right]});
                    // speed up two sum search runtime by removing duplicates 
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left-1]) left++; // you may not need "left<right"
                    //here in C++

                    while(left < right && nums[right] == nums[right+1])right--; // you may not need "left<right" 
                    //here in C++


                }
                else if (sum < twoSumTarget ){
                    left ++;
                }
                else{
                    right--;
                }

            }

        }

        return answer;
    }
};

Special thanks: 洗刷刷 for the reference!