【C++ leetcode】双指针问题

小小小汐- 2024-07-22 17:05:30 阅读 85

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

 代码

<code>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;

}

};



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。