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

1. 有效三角形个数

1.1 题目链接

题目链接

1.2 题目描述

1.3 题目示例

1.4 算法思路

1. 构成三角形的条件：两边之和大于第三边，两边之差小于第三边。验证这两个条件较繁琐，排序后可简化。
2. 当三个数 a、b、c 从小到大排序后，只需满足 a + b > c 即可构成有效三角形。
3. 在排序后的数组中，固定最大的边 nums[k] 作为三角形的第三边，然后在 [0, k-1] 范围内使用对撞指针寻找满足条件的两边。
   • 设置 left = 0 和 right = k-1。当 nums[left] + nums[right] > nums[k] 时，由于数组升序排列，left 到 right-1 的所有位置与当前 right 组成的配对都能满足条件。计数器增加 right - left 个有效组合，然后将 right 左移一位。
   • 如果 nums[left] + nums[right] <= nums[k]，说明两边之和太小，将 left 右移来增加两边之和。

1.5 核心代码

#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--) { // 因为最少三条边，所以 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;
    }
};

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. 一个指向第一个数据，一个指向最后一个数据，然后相加。
3. 如果结果大于 target 说明过大，right--；如果结果小于 target 说明太小，left++；如果相等就返回，直到 left 和 right 指向同一个位置循环停止。

2.5 核心代码

#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 示例测试（总代码）

#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 的两个数字」两个经典问题，展示了双指针在数学组合问题中的精妙应用。掌握这些基础模型后，可进一步挑战三数之和、四数之和等进阶问题，核心思想均为排序预处理加指针智能移动。