15. 3Sum

transform to two sum (in sorted array)

time: O(n^2)

space: O(k), k is the number of solutions

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);
        for (int i = 0; i < nums.length - 2; i++) {
            
            if (i > 0 && nums[i] == nums[i-1]) { // ignore duplicate
                continue;
            }
            
            int target = -nums[i];
            int left = i+1, right = nums.length - 1;
            
            twoSum(res, nums, left, right, target);
        }
        return res;
        
    }
    // transform to two sum problem (in sorted array)
    private void twoSum(List<List<Integer>> res, int[] nums, int left, int right, int target) {
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                
                res.add(Arrays.asList(nums[left], nums[right], -target)); // add ans
                
                left++; // move into central at the same time, why, because only move one side, the value just equ...
                right--;
                while (left < right && nums[left] == nums[left-1]) { // ignore duplicate
                    left++;
                }
                while (left < right && nums[right] == nums[right+1]) { // ignore duplicate
                    right--;
                }
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
}
/*
brute force: O(n^3), three for loop to find ans

so optimized solution is: 
makes it like two sum: O(n^2)
a + b + c == 0

a + b = -c, become two sum(sorted), a+b find target -c

1. sort data
2. for (i = 0, ..i < nums.length -2...) target = -num[i]
3. two sum, but this need skip duplicate value

cant have duplicate ans
*/