《算法题讲解指南：优选算法-双指针》--05有效三角形的个数，06查找总价值为目标值的两个商品
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
05.有效三角形的个数
题目链接：
611. 有效三角形的个数 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（排序+双指针）
算法思路：
先将数组排序。
判断三角形的优化方法：
- 如果能构成三角形，需要满足任意两边之和大于第三边。但是实际上只需要让较小的两条边之和大于第三边即可
根据【上述优化思想】我们可以固定一个【最长边】，然后在比这条边小的有序数组中找出一个二元组，使得这个二元组之和大于这个最长边。由于数组是有序的，我们可以利用【对撞指针】来优化。
设最长边枚举到 i 位置 ，区间 【left，right】 是 i 位置左边的区间（也就是比它小的区间）：
1.如果 nums[ left ] + nums[ right ] > nums[ i ];
- 说明【left，right - 1】区间上的所有元素均可以与 nums[ right ] 构成比 nums[ i ] 大的二元组
- 满足条件的有 right - left 种
- 此时 right 位置的元素的所有情况相当于全部考虑完毕，right--，进入下一轮判断
2.如果 nums[ left ] + nums[ right ] <= nums[ i ]
- 说明 left 位置的元素是不可能与 【left + 1，right】位置上的元素构成满足条件的二元组
- left 位置的元素可以舍去， left++ 进去下轮循环
C++代码演示：
class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); int c = nums.size() - 1; int ret = 0; while(c > 1) { int left = 0; int right = c - 1; while(left < right) { if(nums[left] + nums[right] > nums[c]) { ret += (right - left); right--; } if(nums[left] + nums[right] <= nums[c]) { left++; } } c--; } return ret; } };算法总结及流程解析：
06.查找总价值为目标值的两个商品
题目链接：
LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（双指针-对撞指针）
算法思路：
注意到本题是升序的数组，因此可以用【对撞指针】优化时间复杂度。
算法流程：
1.初始化 left，right 分别指向数组的左右两端（这里不是我们理解的指针，而是数组的下标）
2.当 left < right 的时候，一直循环
2.1当 nums[ left ] + nums[ right ] == target 时，说明找到结果，记录结果，并且返回；
2.2当 nums[ left ] + nums[ right ] < target 时：
- 对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的最大值（需要注意数组是升序）。如果此时不符合要求，说明在这个数组里面，没有别的数符合 nums[ left ] 的要求了。因此，我们可以大胆舍去这个数。让 left++，去比较下一组数据；
- 那对于 nums[ right ] 而言，由于此时两数之和是小于目标值的， nums[ right ] 还可以选择比 nums[ left ] 大的值继续努力达到目标值，因此 right 指针我们按兵不动；
3.当 nums[ left ] + nums[ right ] > target 时。同理我们可以舍去 nums[ right ]。让 right-- ，继续比较下一组数据，而 left 指针不变（因为他还是可以去匹配比 nums[ right ] 更小的数）
C++代码演示：
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { vector<int> ret; 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{ ret.push_back(price[left]); ret.push_back(price[right]); break; } } return ret; } };算法总结及流程解析：
结束语
到此，05有效三角形的个数 和 06查找总价值为目标值的两个商品 两道算法题就讲解完了。这两道题所用方法都是基于双指针算法的高效解题方法。强调排序预处理和指针移动策略在优化算法中的关键作用。希望大家能有所收获！
