《算法闯关指南：优选算法-双指针》--05有效三角形的个数，06查找总价值为目标值的两个商品
🔥草莓熊Lotso：个人主页
❄️个人专栏：《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受。
🎬博主简介：
目录
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
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: vector<int> twoSum(vector<int>& price, int target) { int left=0,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}; } };算法总结&&笔记展示：
笔记字有点丑，大家见谅：
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) { int left=0,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}; } };算法总结&&笔记展示：
笔记字有点丑，大家见谅：
往期回顾：
结语：本篇博客介绍了两个基于双指针算法的高效解题方法。强调排序预处理和指针移动策略在优化算法中的关键作用。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。
✨把这些内容吃透超牛的！放松下吧✨
ʕ˘ᴥ˘ʔ
づきらど
