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

Method

it is a two - sum follow up except two -sum method we need care about more duplicate to avoid duplicate triplets;

Time and Space Complexity

o(n^2)

Code

public class Solution {

   public List<List<Integer>> threeSum(int[] nums) {
       List<List<Integer>> ans = new ArrayList<List<Integer>>();

       if (nums == null || nums.length == 0){
           return ans;
       }

       Arrays.sort(nums);
       for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int k = i + 1;
            int m = nums.length - 1;
            int target = 0 - nums[i];

            while (k < m){
                  int tmp = nums[k] + nums[m];
                  if (target == tmp){
                      List<Integer> list = new ArrayList<Integer>(Arrays.asList(nums[i], nums[k], nums[m]));
                      ans.add(list);
                      while (k < m && nums[k] == nums[k + 1]) k++;
                      while (k < m && nums[m] == nums[m - 1]) m--;
                      k++;
                      m--;
                  } else if (tmp > target){
                      m--;
                  } else {
                      k++;
                  }

            }
       }
       return ans;
}

}