双指针算法实战：从三角形计数到四数之和

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

题目背景

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

核心思路

这是双指针最基础的应用形式。既然数组已有序，我们无需暴力枚举。

1. 初始化：左指针指向最小值，右指针指向最大值。
2. 比较求和：
   • 若和小于目标值，说明需要更大的数，左指针右移。
   • 若和大于目标值，说明需要更小的数，右指针左移。
   • 若相等，直接返回结果。

代码实现

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]};
    }
};

三数之和

题目背景

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

核心思路

此题可转化为'两数之和'的变体。固定一个数 nums[i]，问题就变成了在剩余部分寻找两数之和为 -nums[i]。

1. 排序：必须排序以便去重和双指针操作。
2. 固定第一个数：遍历数组，将 nums[i] 作为第一个数。若 nums[i] > 0，后续不可能有解（因为数组已升序），可直接终止。
3. 双指针找后两数：在 i+1 到末尾之间寻找和为 -nums[i] 的组合。
4. 去重处理：
   • 外层循环跳过相同的 nums[i]。
   • 内层找到解后，左右指针跳过相同的值，避免重复三元组。

代码实现

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; ) {
            int target = nums[i];
            // 优化：如果当前数大于 0，后续不可能和为 0
            if (target > 0) break;
            
            int left = i + 1, right = n - 1;
            while (left < right) {
                long sum = (long)nums[left] + nums[right];
                if (sum == -target) {
                    ret.push_back({target, 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--;
                }
            }
            // 外层去重
            i++;
            while (i < n - 2 && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

四数之和

题目背景

找出数组中所有和为特定目标值的四元组。

核心思路

四数之和可以看作是三数之和的扩展。固定前两个数，剩下的问题就退化为三数之和。

1. 双重循环固定前两数：外层循环固定第一个数 a，内层循环固定第二个数 b。
2. 转化为三数之和：在剩余元素中寻找和为 target - a - b 的三个数。
3. 复用逻辑：可以直接调用或复用三数之和的双指针逻辑，但需注意边界条件和去重。
4. 去重：每一层循环都需要跳过重复元素，确保结果不重复。

代码实现

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; ) {
            for (int j = i + 1; j < n - 2; ) {
                long currentTarget = (long)target - nums[i] - nums[j];
                int left = j + 1, right = n - 1;
                
                while (left < right) {
                    long sum = (long)nums[left] + nums[right];
                    if (sum == currentTarget) {
                        result.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 < currentTarget) {
                        left++;
                    } else {
                        right--;
                    }
                }
                // 第二层去重
                j++;
                while (j < n - 2 && nums[j] == nums[j - 1]) j++;
            }
            // 第一层去重
            i++;
            while (i < n - 3 && nums[i] == nums[i - 1]) i++;
        }
        return result;
    }
};

总结

双指针的核心在于利用数据的单调性来减少搜索空间。在处理此类问题时，务必注意以下几点：

• 排序是前提：大多数双指针问题依赖有序性。
• 边界检查：特别是循环终止条件和数组越界风险。
• 去重策略：在存在重复元素时，需在移动指针时跳过相同值，防止结果冗余。
• 类型溢出：涉及数值求和时，注意使用长整型避免溢出。