双指针算法进阶：有效三角形、两数及多数之和

2. 查找总价格为目标值的两个商品

题目描述

在一个升序数组中，找到两个数使其和等于目标值 target。

核心思路

这是最经典的双指针模型。由于数组已有序，我们可以用左右指针向中间逼近：

• 若 sum < target，说明需要更大的数，left++。
• 若 sum > target，说明需要更小的数，right--。
• 若相等，直接返回结果。

代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, right = price.size() - 1;
        while (left < right) {
            if (price[left] + price[right] < target)
                left++;
            else if (price[left] + price[right] > target)
                right--;
            else
                break;
        }
        return {price[left], price[right]};
    }
};

3. 三数之和

题目描述

找出数组中所有和为 0 的不重复三元组。

核心思路

将问题转化为两数之和：固定一个数 nums[i]，目标变为在剩余部分找两数和为 -nums[i]。

关键点：

1. 去重：排序后相同数字相邻。若 nums[i] == nums[i-1]，跳过；找到解后，移动 left 和 right 时需跳过重复值。
2. 剪枝：若 nums[i] > 0，后续不可能有和为 0 的组合，可直接结束。

代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        
        for (int i = 0; i < n - 2; i++) {
            // 剪枝：若当前数大于 0，后续不可能和为 0
            if (nums[i] > 0) break;
            // 去重：跳过相同的起始元素
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int left = i + 1, right = n - 1;
            while (left < right) {
                long sum = (long)nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    // 去重：跳过重复的左右指针元素
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++, right--;
                }
            }
        }
        return ret;
    }
};

4. 四数之和

题目描述

找出数组中所有和为 target 的不重复四元组。

核心思路

在三数之和的基础上再嵌套一层循环。固定第一个数 nums[i]，问题转化为在剩余部分找三数之和为 target - nums[i]。

同样需要注意去重逻辑，且为了防止整数溢出，计算和时应使用 long 类型。

代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        int n = nums.size();
        
        for (int i = 0; i < n - 3; i++) {
            // 剪枝与去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                
                int left = j + 1, right = n - 1;
                long t = (long)target - nums[i] - nums[j];
                
                while (left < right) {
                    long sum = (long)nums[left] + nums[right];
                    if (sum < t) {
                        left++;
                    } else if (sum > t) {
                        right--;
                    } else {
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++, right--;
                    }
                }
            }
        }
        return result;
    }
};

以上四种情况展示了双指针在处理定和组合问题时的通用模式：排序 + 固定 + 双指针逼近 + 去重。掌握这一套路，面对类似的 K 数之和问题也能快速上手。