18. 4Sum

pin two num[i], nums[j], then two sum

same as 3sum, just pin one more number, one more for loop

O(n^3)

O(k), number of solutions

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        
        // pin two num[i], nums[j]
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for (int j = i+1; j < nums.length - 2; j++) {
                if (j > i+1 && nums[j] == nums[j-1]) {
                    continue;
                }
                
                int left = j+1;
                int right = nums.length - 1;
                twoSum(res, nums, left, right, nums[i], nums[j], target);
            }
        }
        return res;
        
    }
    
    private void twoSum(List<List<Integer>> res, int[] nums, int left, int right, int numi, int numj, int target) {
        while (left < right) {
            int sum = nums[left] + nums[right] + numi + numj;
            
            if (sum == target) {
                res.add(Arrays.asList(nums[left], nums[right], numi, numj));
                
                left++;
                right--;
                while (left < right && nums[left] == nums[left-1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right+1]) {
                    right--;
                }
                
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
}

/*
pin two pointers
then two sum
*/