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

一刷
有两种思路。

1. 先排序再用双指针
   Time complexity O(n^2), space complexity O(1)

2. 使用Two Sum的方法， 遍历 + HashMap
   Time complexity O(n^2), space complexity O(n)

HashMap 在我们需要返回indices比较有用，因为sort之后indices无法一一对应

方法1:

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length<3) return res;
        Arrays.sort(nums);
        //eliminate the duplicate ones
        for(int i=0; i<nums.length-2; i++){
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int lo = i+1;
            int hi = nums.length - 1;
            while(lo < hi){
                if(nums[i] + nums[lo] + nums[hi] == 0){
                    Integer[] array = {nums[i], nums[lo], nums[hi]};
                    res.add(Arrays.asList(array));
                    hi--;
                    while(hi>=0 && nums[hi] == nums[hi+1]) hi--;
                    lo++;
                    while(lo<nums.length && nums[lo] == nums[lo-1]) {
                        lo++;
                    }
                }
                else if(nums[i] + nums[lo] + nums[hi] > 0){
                     hi--;
                }
                else {
                    lo++;
                }
            }
        }
        return res;
    }
}