15. 3Sum

Question:

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

Given array nums = [-1, 0, 1, 2, -1, -4],

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

Thinking:

  • Method1: Two pointer iterate the array in order, use left and right pointers to represent the index of the other two numbers. 
      class Solution {
      public List<List<Integer>> threeSum(int[] nums) {
          Arrays.sort(nums);
          int len = nums.length;
          List<List<Integer>> result = new ArrayList<List<Integer>>();
          for(int i = 0; i < len - 2; i++){
              if(i > 0 && nums[i] == nums[i-1]) continue;//Check current and previous, if duplicate, skip.
              int left = i + 1;
              int right = len - 1;
              int target = -nums[i];
              while(left < right){	//break utill left and right pointer superpose.
                  if(nums[left] + nums[right] == target){
                      result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                      left ++; right --;
                      //Remove duplicate left and right
                      while(left < right && nums[left - 1] == nums[left])    left++;
                      while(right > left && nums[right + 1] == nums[right])    right--;
                  }else if(nums[left] + nums[right] < target){//nums is in order
                      left++;
                  }else   right--;
              }
          }
          return result;
      }
  }

二刷

  1. 使用双指针。如果和大于0，则左移高位，小于0则右移低位。
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        int low = 0, high = 0, sum = 0;
        for(int i = 0; i < nums.length - 2; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int n1 = nums[i];
            low = i + 1; high = nums.length - 1;
            while(low < high){
                sum = n1 + nums[low] + nums[high];
                if(sum == 0){
                    if(low > i + 1 && nums[low] == nums[low - 1]){
                        low++;continue;
                    }else if(high < nums.length - 1 && nums[high] == nums[high + 1]){
                        high--;continue;
                    }
                    result.add(Arrays.asList(n1, nums[low], nums[high]));
                    low ++; high--;
                }else if(sum > 0)
                    high --;
                else
                    low++;
            }
        }
        return result;
    }
}

Amazon session

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);  //O(NlgN)
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < nums.length - 2; i++){   //O(n)
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int slow = i + 1, fast = nums.length - 1;
            int target = -nums[i];
            while(slow < fast){ //O(n)
                int sum = nums[slow] + nums[fast];
                if(sum == target){
                    res.add(Arrays.asList(nums[i], nums[slow], nums[fast]));
                    while(slow < fast && nums[slow] == nums[slow + 1]){
                        slow++;
                    }
                    while(slow < fast && nums[fast] == nums[fast - 1]){
                        fast--;
                    }
                    slow ++;
                    fast --;
                }else if(sum < target){
                    slow++;
                }else{
                    fast--;
                }
            }
        }
        return res;
    }
}