【C++】优选算法必修篇之双指针实战：有效三角形个数 & 和为s的两个数字
【C++】优选算法必修篇之双指针实战：有效三角形个数 & 和为s的两个数字
双指针应用场景
应用场景介绍----------<----------链接直达请点击
目录
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>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 算法思路
- 因为这个数组题目中已经说明是升序了，我们可以同样可以采用对撞指针来实现。
- 一个指向第一个数据，一个指向最后一个数据，然后让他们相加。如果结果大于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++】优选算法必修篇之双指针实战：三数之和 & 四数之和