网站内链建设和外链的推广,用电脑记事本做网站,短视频运营基础知识,中国外协加工网最新加工订单欢迎来到 CILMY23的博客
#x1f3c6;本篇主题为#xff1a;双指针算法之LCR 179. 查找总价格为目标值的两个商品#xff08;力扣#xff09;
#x1f3c6;个人主页#xff1a;CILMY23-CSDN博客
#x1f3c6;系列专栏#xff1a;Python | C | C语言 | 数据结构与算法… 欢迎来到 CILMY23的博客
本篇主题为双指针算法之LCR 179. 查找总价格为目标值的两个商品力扣
个人主页CILMY23-CSDN博客
系列专栏Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux | 算法专题 | 代码训练营
感谢观看支持的可以给个一键三连点赞收藏评论。如果你觉得有帮助还可以点点关注 题目
LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。
示例 一、题目解析 根据题目给出的信息一共有以下几点 1.price数组中的数据是升序排列 2.在数组中找两个数求和 3.存在多种情况返回任一结果即可 ---找一个结果就行 4.情况中可能没有结果 在之前的磨练里这种要找两个数并且求和的它是需要两个指针所以这题为双指针算法
二、算法原理 这题的解法跟之前的几篇写过的原理相似。
我们可以先想想暴力破解是如何做的 这题双循环然后给它记录下来一个数一个数的遍历过去这样暴力破解的思路大致清晰了。
因为存在多种情况返回任一结果即可 ---找一个结果就行。
暴力破解的复杂度是O(n^2),我们可以采用双指针算法来减少空间复杂度达到O(n)。 解析
我们让一个left指向第一个数right指向第二个数如果他们加起来和target 给的数相等那么我们就返回这两个数。
假设 left right 18那说明left太小了可以增加left的值因为数组是单调递增所以先增加最小的值故让left。
假设 left right 18那说明right太小了可以增加right的值因为数组是单调递增所以先减小最大的值故让right--。
那如果没有结果我们就返回一个{}就可以了。
三、代码编写
class Solution
{
public:vectorint twoSum(vectorint price, int target){int left 0;int right price.size() -1;while(left right){if(price[left] price[right] target ){return {price[left],price[right]};}else if(price[left] price[right] target){left;}else if(price[left] price[right] target){right--;}}return {};}
}; ️感谢各位同伴的支持本期C算法专题就讲解到这啦下期我们将详解三数之和如果你觉得写的不错的话可以给个一键三连点赞收藏评论可以的话还希望点点关注若有不足欢迎各位在评论区讨论。
