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

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

双指针是处理数组类问题的利器，尤其在有序数组中，利用单调性可以大幅降低时间复杂度。本文将通过两个经典题目——「有效三角形个数」和「和为 S 的两个数字」，深入剖析对撞指针的应用逻辑。

1. 有效三角形个数

1.1 题目描述

给定一个包含非负整数的数组 nums，返回其中能组成三角形的三元组个数。

1.2 思路分析

构成三角形的条件是任意两边之和大于第三边。对于三个数 a, b, c（假设已排序 a <= b <= c），只需满足 a + b > c 即可。

算法核心步骤如下：

1. 排序：首先将数组升序排列。
2. 固定最长边：从后往前遍历，固定最大的边 nums[k]。
3. 双指针查找：在 [0, k-1] 区间内使用左右指针 left 和 right。
   • 若 nums[left] + nums[right] > nums[k]，说明当前 right 与 left 到 right-1 之间的所有元素组合均满足条件（因为数组有序）。此时计数增加 right - left，并将 right 左移。
   • 若 nums[left] + nums[right] <= nums[k]，说明两边之和太小，需增大较小的一边，将 left 右移。

1.3 代码实现

#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 题目描述

给定一个升序排列的整数数组 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;
}

总结

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