15. 3Sum.md

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;
    }
}