015-3sum

Question

https://leetcode.com/problems/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.

Example:

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Thought Process

1. Brute force
   1. Triple loop and use set to eliminate the duplicates by sorting the solution
   2. Time complexity is O(n^3)
   3. Space complexity is O(1)
2. Two Pointers
   1. Sort the array
   2. Loop through the elements, if the current element is equal to the last element, we skip it to avoid duplicate solution
   3. Set the pointer to the next element and the last element of remaining elements
   4. Time complexity is O(n^2)
   5. Space complexity is O(1)

Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length < 3) return result;
        Arrays.sort(nums);
        for(int i =0; i< nums.length - 2; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int lo = i + 1;
            int hi = nums.length - 1;
            while(lo < hi){
                int sum = nums[i] + nums[lo] + nums[hi];
                if(sum == 0){
                    List<Integer> sol = new ArrayList<>();
                    sol.add(nums[i]);
                    sol.add(nums[lo]);
                    sol.add(nums[hi]);
                    result.add(sol);
                    while(lo < hi && nums[lo] == nums[lo+1]) lo++;
                    while(lo < hi && nums[hi] == nums[hi-1]) hi--;
                    lo++;
             hi--;
                } else if(sum < 0){
                    lo++;
                } else{
                    hi--;
                }
            }
        }
        return result;
    }
}

Additional