双指针算法进阶：从三角形到多数之和

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

核心思路 这是经典的'两数之和'变体。由于题目保证数组已排序，我们不需要哈希表，直接用双指针即可。

解题步骤

1. 初始化：左指针指向最小值，右指针指向最大值。
2. 比较求和：
   • 和小于目标值：left++（需要更大的数）。
   • 和大于目标值：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. 三数之和（LeetCode 15）

核心思路 将问题转化为'两数之和'。固定一个数 nums[i]，问题就变成了在剩余数组中找两数之和等于 -nums[i]。

关键点

• 去重：这是最容易出错的地方。如果 nums[i] == nums[i-1]，跳过当前循环；当找到一组解后，左右指针也要跳过相同的值。
• 剪枝：如果固定的数 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;
    }
};

4. 四数之和（LeetCode 18）

核心思路 在三数之和的基础上再嵌套一层循环。固定第一个数 nums[i]，剩下的问题就是找三数之和等于 target - nums[i]。

实现细节

• 同样需要处理去重逻辑，防止结果集重复。
• 注意整数溢出问题，计算过程中建议转换为 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;
                long long sum = (long long)nums[i] + nums[j];
                long long remain = (long long)target - sum;
                
                while (left < right) {
                    long long currentSum = (long long)nums[left] + nums[right];
                    if (currentSum < remain) {
                        left++;
                    } else if (currentSum > remain) {
                        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;
    }
};

通过这四个例子可以看出，双指针的核心在于利用有序性减少搜索空间。只要掌握'固定一端、移动另一端'以及'去重'这两个要点，就能应对大部分此类变种问题。