C++ 双指针算法实战：有效三角形个数与和为 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();
        int ret = 0;
        for (int i = n - 1; i >= 2; i--) {
            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]};
            }
        }
        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);
    cout << "[";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << ",";
        }
    }
    cout << "]" << endl;
    return 0;
}

总结

本文通过「有效三角形个数」和「和为 s 的两个数字」两个经典问题，展示了双指针在数学组合问题中的精妙应用。核心思想在于排序预处理 + 指针智能移动。掌握这些基础模型后，可进一步挑战三数之和、四数之和等进阶问题，体会分治思想在算法设计中的威力。