LeetCode 4Sum：基於 3Sum 的四數求和去重解法

題目簡介

給定整數數組 S 和目標值 target，找出所有不重複的四元組 (a,b,c,d) 使得 a+b+c+d=target，且 a≤b≤c≤d。

解題思路

排序數組，外層循環固定第一個數 nums[i]，內層調用 3Sum 邏輯在 nums[i+1..end] 中找三數和為 target - nums[i]。去重關鍵：

• 外層：if (i>0 && nums[i]==nums[i-1]) continue;
• 3Sum 內層：固定第二數同理去重；雙指針找第三四數時，跳過重複值。

代碼實現

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        threeSum(nums, i+1, target - nums[i], nums[i], res);
    }
    return res;
}

void threeSum(int[] nums, int start, int target, int first, List<List<Integer>> res) {
    for (int i = start; i < nums.length-2; i++) {
        if (i > start && nums[i] == nums[i-1]) continue;
        int l = i+1, r = nums.length-1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == target) {
                res.add(Arrays.asList(first, nums[i], nums[l], nums[r]));
                while (l < r && nums[l] == nums[l+1]) l++;
                while (l < r && nums[r] == nums[r-1]) r--;
                l++; r--;
            } else if (sum < target) l++;
            else r--;
        }
    }
}

複雜度分析

排序 O(n log n)，外層 O(n)，內層 3Sum O(n^2)，總時間 O(n^3)，空間 O(1) 不計輸出。