15.md

15. 3Sum

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: 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]
]

Thinking process

1. Sort the array, pick one element and call the twoSum subroutine on the rest of the array
2. How to avoid duplicates? (a. HashSet, b. Skip same elements)

public List<List<Integer>> threeSum(int[] nums) {
	Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for(int i=0; i < nums.length; i++){
      	//skip same elements
        if(i > 0 && nums[i] == nums[i-1])
            continue;
        int target = - nums[i];
        int low = i + 1;
        int high = nums.length - 1;
        while(low < high){
            if(nums[low] + nums[high] == target){
                res.add(Arrays.asList(nums[i], nums[low], nums[high]));
              	//skip same elements
                while(low < high && nums[low] == nums[low + 1])
                    low++;
                while(low < high && nums[high] == nums[high - 1])
                    high--;
                low++;
                high--;
            }else if(nums[low] + nums[high] < target)
                low++;
            else
                high--;
        }
    }
    return res;
}

Complexity

1. Sorting takes O(nlogn)
2. Each twoSum procedure takes O(n), needs to be called n times
3. Total complexity is O(n²)