15. 3Sum

Link

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

Solution

這題概念上針對nums[i]尋找其他的任兩點, j, k 使 nums[j] + nums[k] = sum - nums[i]，所以等於是twoSum的變形題。 但找的內容變成是根據nums[i]去改變。

Arrays.sort(nums) 但若沒有sort過，要尋找j, k的範圍就會變成整個nums[]，且有重複計算的可能性。透過sort，可以直接從i+1 開始找j, k。 所以先sort。

此時要注意的是重複值的點只要計算一次就好所以都要skip掉。

ex: 0 , -1,-1,1, [0, -1, 1] [0, -1 ,1] 粗體-1跟正常的-1其實只要算一次就可以，因為其內容都是[0,-1,1]

public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(i == 0 || nums[i] != nums[i-1]){ //skip掉重複值的i
                int target = 0 - nums[i];
                int lo = i+1, hi = nums.length - 1;
                while(lo < hi){
                    if(nums[lo] + nums[hi] == target){
                        ret.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while(lo < hi && nums[lo] == nums[lo+1]) lo++; //skip掉重複值的lo
                        while(lo < hi && nums[hi] == nums[hi-1]) hi--; //skip掉重複值的hi
                        lo++;
                        hi--;
                    }
                    else if (nums[lo] + nums[hi] > target){
                        hi--;
                    }
                    else {
                        lo++;
                    }
                }
            }
        }
        return ret;
    }