【C++】优选算法必修篇之双指针实战：有效三角形个数 & 和为s的两个数字

我不是呆头

发布于 2025-12-20 14:29:56

570

双指针应用场景

应用场景介绍----------<----------链接直达请点击

1. 有效三角形个数

1.1 题目链接

题目链接直达<----------请点击

1.2 题目描述

1.3 题目示例

1.4 算法思路

我们首先得清除构成三角形的条件：两边之和大于第三边，两边之差小于第三边，但是要验证这两个条件好像很麻烦，有没有更简单的方法呢？
当三个数a，b，c我们从小到大排序：然后你会发现只需要满足a + b > c就能构成一个有效的三角形。
在排序后的数组中，我们固定最大的边 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]，说明当前的两边之和太小，需要增大其中一边。由于 right 已经是当前范围内较大的值，我们通过将 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();//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;
    }
};

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 算法思路

因为这个数组题目中已经说明是升序了，我们可以同样可以采用对撞指针来实现。
一个指向第一个数据，一个指向最后一个数据，然后让他们相加。如果结果大于traget说明过大，right–；如果结果小于traget说明太小，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] };
                //等价于vector<int> ans;
                //ans.push_back(price[left]);
                //ans.push_back(price[right]);
                //return ans;
            }
        }
        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;
}