【C++ leetcode】双指针问题

阅读本书更多章节>>>>

1.   611. 有效三角形的个数

题目

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

题目链接

. - 力扣（LeetCode）

画图 和 文字 分析

判断是否是三角形要得到三边，由于遍历三边要套三层循环，时间复杂度很大，所以这里我们需要借助双指针思想，可以降到 O（N * N），先将这个数组进行排序（升序），然后定义三个指针，一个开始固定在数组的最后一个元素的位置，另外两个指向第一个位置和最后一个元素的前一个位置

举例： 输入[4,2,3,4]，输出 4

如图

因为是排好序的，判断的时候，只需要拿 left , right 所指向的元素与 n 所指向的元素进行对比

比较过程会遇到两种情况：

第一种是不能构成三角形，则让 left++ ，

第二种是能构成三角形，则让 count += left - right (如果能构成三角形，则 right 和 n 不变，left 与 right 之间的区间都能构成三角形 ) ，right-- ,

直到 left >= right（里层循环结束条件） , 再 n--， right = n - 1 , left = 0

外出循环结束条件：n < 2

 代码

class Solution {public:    bool IsTriangle(int x,int y,int z)    {        return (x + y) > z;    }    int triangleNumber(vector<int>& nums)     {        sort(nums.begin(),nums.end());        int count = 0;        for(int n = nums.size() - 1;n >=2 ;n--)        {            int left = 0;            int right = n - 1;            while(left < right)            {               if(IsTriangle(nums[left],nums[right],nums[n]))             {                count += (right - left);                right--;             }             else             {                left++;             }            }        }         return count;    }};

2.   LCR 179. 查找总价格为目标值的两个商品

题目

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

题目链接

. - 力扣（LeetCode）

画图 和 文字 分析

思路还是一样，排序 + 双指针

很容易就想到思路，两个指针指向数组的两端

会遇到三种情况：

第一种情况，当大于目标值时，right--

第二种情况，当小于目标值时，left++

第三种情况，等于目标值时，存完数值，break 即可

代码

class Solution {public:    vector<int> twoSum(vector<int>& price, int target)     {        vector<int> t;        int right = price.size() - 1;        int left = 0;        while(left < right)        {            if( price[left] +  price[right] == target )            {               t.push_back(price[left]);               t.push_back(price[right]);               break;            }            else if(price[left] +  price[right] > target)            {                right--;            }            else            {                left++;            }        }        return t;    }};

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-03-25/148657.html，文章来源：网络cs，作者：璐璐，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！