双指针算法进阶：三角形计数与多数求和

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

题目描述

在一个已排序的数组中，找到两个数，使它们的和等于目标值。

解题思路

这其实是两数之和问题的变种。由于数组已经有序，我们可以利用双指针从两端向中间收缩。

• 当两数之和小于目标值时，需要增大和，因此左指针右移；
• 当两数之和大于目标值时，需要减小和，因此右指针左移；
• 相等时直接返回结果。

这种方法的时间复杂度是 O(n)，比哈希表方案更节省空间，且无需额外数据结构。

代码实现

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

三数之和

题目描述

给你一个整数数组 nums，判断是否存在三个元素 a, b, c 使得 a + b + c = 0？找出所有满足条件且不重复的三元组。

解题思路

将问题转化为两数之和：固定一个数 nums[i]，问题就变成了在剩余数组中寻找两数之和为 -nums[i]。

关键点在于去重。由于数组已排序，相同的数字会相邻。

1. 外层循环固定 i 时，如果 nums[i] == nums[i-1]，跳过本次循环。
2. 内层双指针找到解后，移动 left 和 right 时需跳过重复值。
3. 优化：如果 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) {
                int sum = 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;
    }
};

四数之和

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，找出所有不重复的四元组，使其和等于 target。

解题思路

四数之和可以看作是两数之和的扩展。我们可以固定前两个数，将问题转化为在三数之和中求解。

逻辑与三数之和类似：

1. 外层双重循环固定前两个数 i 和 j。
2. 内层使用双指针寻找剩余两个数。
3. 同样需要注意去重逻辑，以及防止整数溢出的处理（使用 long 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;
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        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;
    }
};

通过这四个例子可以看出，双指针的核心在于利用数据的有序性，将时间复杂度从 O(n^3) 或 O(n^4) 降低到 O(n^2)。在实际开发中，遇到涉及'和'、'差'、'乘积'等数值关系的题目，不妨优先考虑排序加双指针的思路。