# 15 3Sum

Concept:

先把整個array sort一遍。

每讀到nums的某element，

用兩個pointer指nums的另外兩個element，當另外兩個element相加= -nums[i]，

加入res。

Pseudocode:

two pointer, start and end.
    for each element in nums,
        start = i+1
        end = nums.length-1
        while(start<end)
            if(nums[start]+ nums[end] == -nums[i])
                put i,start,end into res
                to avoid duplicate,
                while(start < end && num[start] == num[start+1]) start++
                while (start < end && num[end] == num[end-1]) end--;
                start++, end--
            else if nums[start]+ nums[end] > -nums[i]
                end--
            else
                start++

Code:

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        int start, end;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0; i<nums.length-2; i++){
            start = i+1;
            end = nums.length -1;
            while(start < end){
                if(nums[start]+ nums[end] == -nums[i]){
                    if(i==0 || (i>0 && nums[i]!=nums[i-1]))
                        res.add(Arrays.asList(nums[i],nums[start],nums[end]));
                    while(start < end && nums[start] == nums[start+1]) start++;
                    while (start < end && nums[end] == nums[end-1]) end--;
                    start++;
                    end--;
                }else if (nums[start]+ nums[end] > -nums[i])
                    end--;
                else
                    start++;
            }
        }
        return res;
    }
}