【优选算法必刷100题】第005~006题（双指针算法）：有效三角形的个数和查找总价值为目标值的两个商品

用户11915063

发布于 2025-11-20 09:55:34

880

005.有效三角形的个数

题目链接：

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 ret=0,n=nums.size();
        for(int i=n-1;i>=2;i--)
        {
            int left=0,right=i-1;
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[i])
                {
                    ret+=right-left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }    
        return ret;
    }
};

算法总结&&笔记展示：

博主笔记（字迹有点丑，请大家见谅）：

006.查找总价值为目标值的两个商品

题目链接：

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 指针不变

C++代码演示：

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target)
    {
        int left=0,right=price.size()-1;
        while(left<=right)
        {
            int sum=price[left]+price[right];
            if(sum>target) right--;
            else if(sum<target) left++;
            else return {price[left],price[right]};
        }    
        //照顾编译器
        return {-1,-1};
    }
};