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

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

• 双指针应用场景
• 目录
  • 1. 有效三角形个数
    • 1.1 题目链接
    • 1.2 题目描述
    • 1.3 题目示例
    • 1.4 算法思路
    • 1.5 核心代码
    • 1.6 示例测试（总代码）
  • 2. 和为s的两个数字
    • 2.1 题目链接
    • 2.2 题目描述
    • 2.3 题目示例
    • 2.4 算法思路
    • 2.5 核心代码
    • 2.6 示例测试（总代码）
• 总结

双指针应用场景

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

目录

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]，说明当前的两边之和太小，需要增大其中一边。由于 right 已经是当前范围内较大的值，我们通过将 left 右移来增加两边之和。

1.5 核心代码

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;classSolution{public:inttriangleNumber(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>usingnamespace std;classSolution{public:inttriangleNumber(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;}};intmain(){ vector<int> nums1 ={4,2,3,4}; cout <<Solution().triangleNumber(nums1)<< endl;return0;}

2. 和为s的两个数字

2.1 题目链接

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

2.2 题目描述

2.3 题目示例

2.4 算法思路

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

2.5 核心代码

//有效三角形个数，和为s的两个数字#include<iostream>#include<vector>usingnamespace std;classSolution{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--;}elseif(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>usingnamespace std;classSolution{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--;}elseif(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};}};intmain(){ 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;return0;}

总结

在掌握了双指针基础模型（快慢指针、对撞指针）之后，我们进一步探索双指针在数学组合问题中的精妙应用。本篇通过「有效三角形个数」和「和为s的两个数字」两个经典问题。

掌握了这些基础模型后，我们可以进一步挑战：

🔢 三数之和 —— 在二维对撞基础上增加一维遍历，处理更复杂的组合约束
🔢 四数之和 —— 双层循环+对撞指针的组合应用，展现分治思想的威力
🎯 最接近的三数之和 —— 引入差值最小化的优化目标，拓展双指针的适用边界

这些进阶问题都建立在本文所述的核心思想之上——排序预处理 + 指针智能移动，体现了算法设计中"分而治之"的经典智慧。

下一篇，我们将深入探索多指针的高阶应用：
【C++】优选算法必修篇之双指针实战：三数之和 & 四数之和