LeetCode 四數之和：排序 + 多層循環 + 雙指針去重完整解法

題目描述

給定整數數組 nums 和目標值 target，找出所有不重複的四元組 [a, b, c, d]，使 a + b + c + d = target。四元組內元素升序，結果集無重複。

核心思路：排序 + 固定兩層 + 雙指針

推廣自「三數之和」：排序後，固定前兩個數 i, j，剩餘問題轉化為「兩數之和」，用雙指針 left, right 求解。通過跳過重複值保證結果去重。

詳細步驟

1. 排序：sort(nums)
2. 剪枝：
   • 最小四數之和 > target → 直接返回
   • 最大四數之和 < target → 直接返回
3. 三層循環：
   • 第一層 i = 0 .. n-4，跳過重複 nums[i]
   • 第二層 j = i+1 .. n-3，跳過重複 nums[j]
   • 第三、四層合併為雙指針 left = j+1, right = n-1
4. 雙指針查找：
   • sum = nums[i] + nums[j] + nums[left] + nums[right]
   • sum == target：記錄結果，left++ 跳過重複，right-- 跳過重複
   • sum < target：left++
   • sum > target：right--

C++ 完整實現

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        if (n < 4) return res;
        
        sort(nums.begin(), nums.end());
        
        // 全局剪枝
        if (nums[0] + nums[1] + nums[2] + nums[3] > target) return res;
        if (nums[n-1] + nums[n-2] + nums[n-3] + nums[n-4] < target) return res;
        
        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i-1]) continue;  // 去重 i
            
            // 剪枝：i 固定時的最小/最大和
            if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
            if (nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target) continue;
            
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j-1]) continue;  // 去重 j
                
                // 剪枝：i,j 固定時的最小/最大和
                if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
                if (nums[i] + nums[j] + nums[n-1] + nums[n-2] < target) continue;
                
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.push_back({nums[i], nums[j], nums[left], nums[right]});
                        ++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;
                    }
                }
            }
        }
        return res;
    }
};

關鍵優化點

複雜度分析

• 時間：O(n³)，排序 O(n log n)，三層循環 O(n³) 主導
• 空間：O(1) 額外空間（不計輸出），原地排序

推廣到 K 數之和

固定前 K-2 層循環，最後兩層用雙指針。通用框架：

void kSum(vector<int>& nums, int start, int k, long long target, vector<int>& path, vector<vector<int>>& res) {
    if (k == 2) {  // 兩數之和：雙指針
        int l = start, r = nums.size() - 1;
        while (l < r) { ... }
        return;
    }
    for (int i = start; i <= nums.size() - k; ++i) {
        if (i > start && nums[i] == nums[i-1]) continue;
        path.push_back(nums[i]);
        kSum(nums, i+1, k-1, target - nums[i], path, res);
        path.pop_back();
    }
}

掌握「排序 + 固定前 K-2 個 + 雙指針 + 多層去重剪枝」模板，可解決所有 K 數之和變體問題。