双指针算法实战：三数之和与四数之和详解

四数之和

题目解析

四数之和是三数之和的自然扩展。给定一个数组和一个目标值 target，找出所有和为 target 的四元组。

算法原理

核心思想不变，只是多了一层循环：

1. 排序数组。
2. 第一层循环固定第一个数 a。
3. 第二层循环固定第二个数 b。
4. 在 b 之后使用双指针寻找剩余两个数，使它们的和等于 target - a - b。

注意事项

• 整数溢出：计算目标和时，target - a - b 可能会超出 int 范围，建议使用 long long 存储中间结果。
• 多重去重：除了左右指针的去重，外层两个循环变量 a 和 b 也需要跳过重复值。

代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();

        for (int a = 0; a < n; ) {
            for (int b = a + 1; b < n; ) {
                // 使用 long long 防止累加溢出
                long long _target = (long long)target - nums[a] - nums[b];
                int left = b + 1;
                int right = n - 1;

                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum < _target) {
                        left++;
                    } else if (sum > _target) {
                        right--;
                    } else {
                        ret.push_back({nums[a], nums[b], nums[left], nums[right]});
                        left++, right--;
                        // 内层去重
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                
                // 第二层去重
                b++;
                while (b < n && nums[b] == nums[b - 1]) b++;
            }
            
            // 第一层去重
            a++;
            while (a < n && nums[a] == nums[a - 1]) a++;
        }
        return ret;
    }
};

总结

这两道题具有高度相似性，都是排序 + 双指针的经典应用。

• 三数之和：固定一个数，双指针找两个数。
• 四数之和：固定两个数，双指针找两个数。

关键点在于去重逻辑的实现顺序：先处理内层指针，再处理外层循环变量。掌握这个模式后，类似的 k 数之和问题也可以迎刃而解。