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

2024-03-09 08:12

本文主要是介绍LCR 179. 查找总价格为目标值的两个商品 - 力扣,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 题目

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

2. 示例

3. 分析 

我们首先想到暴力解法,这道题目的暴力还是比较简单的,列举每个数的情况即可:

for(int i = 0; i < pricee.size(); i++)for(int j = i + 1; j < price.size(); j++)check(pirce[left], price[right]);// 判断

 暴力解法在这道题目中会超时,所以放弃这个解法。


题目有说明为递增数组,所以可以利用单调性+双指针解决。跟611. 有效的三角形个数为一类题目。

解题方法:

先定义两个指针指向数组左右,它们的和有三种情况:

  • sum > target
    price[right]为数组内的最大值,price[left]为最小,所以此时[left+1, right-1]这个区间的数分别加上price[right]的和是肯定会超过target的,因为题目已经说明数组为递增的最小加上最大都大于target,所以price[left] (最小)右边区间的数也肯定会大于target了。所以直接舍弃掉此时的最小值,再left++即可。
  • sum < target
    price[right]为数组内的最大值,price[left]为最小,所以此时[left+1, right-1]这个区间的数分别加上price[left]的和是肯定不会超过target的,因为题目已经说明数组为递增的,最小加上最大都没有大于target,所以price[right] (最大)左边区间的数也肯定会小于target了。所以直接舍弃掉此时的最大值,再right--即可。
  • sum == target
    返回结果即可

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};// 题目莫得要求无结果需返回什么,所以随便返回两个负数即可}
};

这篇关于LCR 179. 查找总价格为目标值的两个商品 - 力扣的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/790062

相关文章

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

Redis中如何实现商品秒杀

《Redis中如何实现商品秒杀》:本文主要介绍Redis中如何实现商品秒杀问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录技术栈功能实现步骤步骤一:准备商品库存数据步骤二:实现商品秒杀步骤三:优化Redis性能技术讲解Redis的List类型Redis的Set

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

java两个List的交集,并集方式

《java两个List的交集,并集方式》文章主要介绍了Java中两个List的交集和并集的处理方法,推荐使用Apache的CollectionUtils工具类,因为它简单且不会改变原有集合,同时,文章... 目录Java两个List的交集,并集方法一方法二方法三总结java两个List的交集,并集方法一

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多