C++ 双指针实战：有效三角形个数与和为 S 的两个数字

2. 和为 S 的两个数字

2.1 题目描述

给定一个升序排列的整数数组 price 和一个目标值 target，找出两个数使得它们的和等于目标值。如果存在多组解，返回任意一组；不存在则返回 {-1, -1}。

2.2 思路分析

由于输入数组已经是有序的，我们可以直接使用对撞指针：

1. 初始化 left = 0，right = price.size() - 1。
2. 计算 sum = price[left] + price[right]。
   • 若 sum > target，说明和太大，right 左移减小数值。
   • 若 sum < target，说明和太小，left 右移增大数值。
   • 若 sum == target，找到答案，直接返回。
3. 循环直到 left >= right。

2.3 代码实现

#include <iostream>
#include <vector>

using namespace std;

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

int main() {
    vector<int> nums1 = {3, 9, 12, 15};
    vector<int> result = Solution().twoSum(nums1, 18);
    
    cout << "[";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    return 0;
}

总结

这两个问题展示了双指针在数学组合中的典型用法：排序预处理 + 指针智能移动。这种模式不仅解决了当前问题，也是后续学习「三数之和」、「四数之和」等进阶题目的基石。掌握这一思想，能帮助我们在面对复杂约束时快速找到最优解路径。