3 sum

3 sum 這題要求我們從數組找出 a + b + c = target 的所有不重複的可能，

馬上想到的是遍歷數組，然後在當前元素之後的數組進行 2 sum

結果還要排序，所以一開始我們會想要把數組排序，但是避不開重複的狀況

EX: [1, 2, 2, 2, 2, 3, 4] target = 9 => 在第一個 2 會找到 [3,4]，第二個 2 也會

因此遍歷時，遇到與前面相同的數字就要跳下一個

在找 2 sum時也一樣，我們會用兩根指針去找 2 sum，每當找到一組時，會去找下一組，

這裡也要注意不能重複，如果跟前一個一樣還是有可能會找到重複的解

複雜度為 O(n^2)

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 3) {
        return result;
    }
    Arrays.sort(nums);
    for (int i=0; i<nums.length-2; i++) {
        if (i > 0 && nums[i-1] == nums[i]) {
            continue;
        }
        int left = i+1;
        int right = nums.length-1;
        twoSum(nums, nums[i], left, right, 0-nums[i], result);
    }
    return result;
}

private void twoSum(int[] nums,
                            int first, 
                            int left, 
                            int right, 
                            int target,
                            List<List<Integer>> result) 
{
    while(left < right) {
        if (nums[left] + nums[right] == target) {
            List<Integer> res = new ArrayList<>();
            res.add(first);
            res.add(nums[left]);
            res.add(nums[right]);
            result.add(res);
            left++;
            right--;
            // to skip duplicate elemtnt ex: [1, 2, 2, 2, 2, 3, 3, 3, 3 ...]
            while (left < right && nums[left-1] == nums[left]) left++;
            while (left < right && nums[right+1] == nums[right]) right--;
        }
        else if (nums[left] + nums[right] > target) {
            right--;
        } else {
            left++;
        }
    }
}