18. 4Sum - Medium

前往題目

想法

• 3 sum是固定一個數字，然後就變成2 sum問題；那4 sum要固定兩個數字？

思路

1. 先排序(這樣才能輕鬆跳過重複的數字)
2. 當不確定的數字超過2個，就固定當前數字然後再次呼叫方法(Recursion)
3. 當不確定的數字只剩2個，就變成2sum問題，找出哪兩個相加等於target就是答案之一並加入結果

Code

class Solution {
    List<List<Integer>> res;
    List<Integer> quadTmp;
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // Result arraylist
        res = new ArrayList<>();
        // Temp quadruplets
        quadTmp = new ArrayList<>();
        Arrays.sort(nums);
        kSum(4, 0, (long) target, nums);
        return res;
    }

    private void kSum(int k, int start, long target, int[] nums) {
        // Non 2sum problem
        if (k != 2) {
            // At least left 3 numbers
            for (int i = start; i < nums.length - k + 1; ++i) {
                // Skip equals, cuz need unique quadruplets
                if (i > start && nums[i] == nums[i - 1]) continue;
                // Add to the tmp
                quadTmp.add(nums[i]);
                // Call to process 3 sum problem
                // i + 1 => start from next index
                // target - nums[i] => remaining number
                kSum(k - 1, i + 1, target - nums[i], nums);
                quadTmp.remove(quadTmp.size() - 1);
            }
            // Completed processing 4 sum problem
            return;
        }

        // 2 sum problem
        int l = start, r = nums.length - 1;

        while (l < r) {
            if (nums[l] + nums[r] > target) {
                --r;
            } else if (nums[l] + nums[r] < target) {
                ++l;
            } else { // equal
                // Found a combination, adding to the result
                ArrayList<Integer> comb = new ArrayList();
                comb.addAll(quadTmp);
                comb.add(nums[l]);
                comb.add(nums[r]);
                res.add(comb);
                // Move a pointer
                ++l;
                // Skip duplicate
                while (l < r && nums[l] == nums[l - 1]) {
                    ++l;
                }
            }
        }
    }
}