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

1.6 示例测试（总代码）

// 有效三角形个数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 升序排序
        int n = nums.size(); // n 为数组大小
        int ret = 0;
        for (int i = n - 1; i >= 2; i--) // 因为最少三条边，所以 i>=2
        {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
};

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

2. 和为 s 的两个数字

2.1 题目链接

题目链接直达

2.2 题目描述

2.3 题目示例

2.4 算法思路

1. 因为这个数组题目中已经说明是升序了，我们可以同样可以采用对撞指针来实现。
2. 一个指向第一个数据，一个指向最后一个数据，然后让他们相加。如果结果大于 target 说明过大，right--；如果结果小于 target 说明太小，left++；如果相等就返回，直到 left 和 right 指向同一个位置循环停止。

2.5 核心代码

// 和为 s 的两个数字
#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]}; // 等价于 vector<int> ans; ans.push_back(price[left]); ans.push_back(price[right]); return ans;
            }
        }
        return {-1, -1};
    }
};

2.6 示例测试（总代码）

// 和为 s 的两个数字
#include <iostream>
#include <vector>
#include <algorithm>
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); // 正确输出 vector 的方式
    cout << "[";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << ",";
        }
    }
    cout << "]" << endl;
    return 0;
}

总结

在掌握了双指针基础模型（快慢指针、对撞指针）之后，我们进一步探索双指针在数学组合问题中的精妙应用。本篇通过「有效三角形个数」和「和为 s 的两个数字」两个经典问题，展示了排序预处理结合指针智能移动的核心思想。