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

示例测试

int main() {
    vector<int> nums1 = {4, 2, 3, 4};
    cout << Solution().triangleNumber(nums1) << endl;
    return 0;
}

2. 和为 s 的两个数字

题目描述

在一个递增排序的数组中找出两个数，使它们的和等于给定的目标值 target。

算法思路

1. 由于数组已排序，使用对撞指针。
2. 左指针指向首元素，右指针指向尾元素。
3. 计算两数之和：
   • 若 sum > target，right--（减小和）。
   • 若 sum < target，left++（增大和）。
   • 若 sum == target，返回结果。

核心代码

#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) {
            if (price[left] + price[right] > target) {
                right--;
            } else if (price[left] + price[right] < 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;
}

总结

掌握双指针基础模型后，可进一步应用于三数之和、四数之和等进阶问题。核心思想在于排序预处理配合指针的智能移动，体现分治思想。