Three Sum

Description:

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: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets.

Solution

The idea is to simplify the three sum question to a two sum question. Set 0-a as the target, and then do a bi-directional scan of the rest elements in the array.

• Time: O(n2)

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0 ; i < nums.length - 1; i ++) {
            if(i == 0 || (i > 0 && nums[i] != nums[i-1])) {
                int lo = i + 1, hi = nums.length - 1;
                int target = 0 - nums[i];
                while(lo < hi) {
                    if(nums[lo] + nums[hi] == target) {
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[lo]);
                        tmp.add(nums[hi]);
                        res.add(tmp);
                        while(lo < hi && nums[hi] == nums[hi - 1]) hi--;
                        while(lo < hi && nums[lo] == nums[lo + 1]) lo++;
                        hi--; lo++;
                    } else if (nums[lo] + nums[hi] < target) {
                        lo ++;
                    } else hi --;
                }
            }
        }
        return res;
    }
}