【力扣】查找总价格为目标值的两个商品,双指针法

查找总价格为目标值的两个商品原题地址

方法一:双指针

这道题和力扣第一题“两数之和”非常像,区别是这道题已经把数组排好序了,所以不考虑暴力枚举和哈希集合的方法,而是利用单调性,使用双指针求解

考虑数组price的2个下标left和right,对于[left,right],有C_{right-left+1}^{2}种配对方法,我们需要利用单调性剔除一些可能

不妨设price[left]+price[right]<target,考虑[left+1,right-1]范围内的下标(记为m),有price[left]+price[m]<price[left]+price[right]<target,所以left不可能与[left+1,right]的任何下标配对,此时让left右移,在[left+1,right]的范围内寻找配对。同理,若price[left]+price[right]>target,考虑right和[left+1,right-1]范围内的下标(记为n),有price[right]+price[n]>price[right]+price[left]>target,所以right不可能与[left,right-1]的任何下标配对,此时让right左移,在[left,right-1]的范围内寻找配对

反复执行上述操作,直到left=right或者找到符合price[left]+price[right]=target的配对。

// 方法一:双指针
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, right = price.size() - 1;

        while (left < right)
        {
            if (price[left] + price[right] < target)
            {
                ++left;
            }
            else if (price[left] + price[right] > target)
            {
                --right;
            }
            else
            {
                return { price[left], price[right] };
            }
        }

        return {};
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/376923.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

洛希极限

L1-3 洛希极限 分数 10 作者 陈越 单位 浙江大学 科幻电影《流浪地球》中一个重要的情节是地球距离木星太近时&#xff0c;大气开始被木星吸走&#xff0c;而随着不断接近地木“…

【数据结构】链表OJ面试题2《分割小于x并排序链表、回文结构、相交链表》+解析

1.前言 前五题在这http://t.csdnimg.cn/UeggB 休息一天&#xff0c;今天继续刷题&#xff01; 2.OJ题目训练 1. 编写代码&#xff0c;以给定值x为基准将链表分割成两部分&#xff0c;所有小于x的结点排在大于或等于x的结点之前 。链表分割_牛客题霸_牛客网 思路 既然涉及…

春节回家坐飞机后助听器就不好用了?如何过安检、拖运?

春节即将来临&#xff0c;很多人都要乘坐飞机回家或者出游。如果你是一位助听器使用者&#xff0c;你可能会有一些疑问&#xff1a;坐飞机能戴助听器吗&#xff1f;助听器会不会受到安检设备的影响&#xff1f;直接将助听器放在传送带上可以吗&#xff1f;……别担心&#xff0…

Harbor介绍、整体架构和安装

Harbor介绍、整体架构和安装 文章目录 Harbor介绍、整体架构和安装1.Harbor介绍2.Harbor 整体架构3.安装Harbor3.1 主机初始化3.1.1 设置ip地址3.1.2 配置镜像源3.1.3 关闭防火墙3.1.4 禁用SELinux3.1.5 禁用swap3.1.6 设置时区 3.2 安装docker3.3 安装docker compose3.4 下载H…

【JS逆向一】逆向某站的 加密参数算法--仅供学习参考

逆向日期&#xff1a;2024.02.06 使用工具&#xff1a;Node.js 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 可使用AES进行解密处理&#xff08;直接解密即可&#xff09;&#xff1a;在线AES加解密工具 1、打开某某网站(请使用文章开头的…

记录 | linux下切换python版本

查看系统中存在的 python 版本 ls /usr/bin/python* 查看系统默认的 python 版本 python --version

金融信贷风控特征计算详解

特征的含义&#xff1f; 特征可以说是风控系统中的最小单元&#xff0c;是风控工具的重要组成部分&#xff0c;我们也可以理解成变量。不过叫什么问题不大&#xff0c;团队内有相同的共识就行。 风控特征是我们做数字化线上风控中的重要组成部分&#xff0c;几乎可以说没有风…

【Flink入门修炼】1-2 Mac 搭建 Flink 源码阅读环境

在后面学习 Flink 相关知识时&#xff0c;会深入源码探究其实现机制。因此&#xff0c;需要现在本地配置好源码阅读环境。 本文搭建环境&#xff1a; Mac M1&#xff08;Apple Silicon&#xff09;Java 8IDEAFlink 官方源码 一、 下载 Flink 源码 github 地址&#xff1a;h…

[每周一更]-(第85期):NLP-实战操作-文本分类

NLP文本分类的应用场景 医疗领域 - 病历自动摘要&#xff1a; 应用&#xff1a; 利用NLP技术从医疗文档中自动生成病历摘要&#xff0c;以帮助医生更快速地了解患者的状况。 法律领域 - 法律文件分类&#xff1a; 应用&#xff1a; 使用文本分类技术自动分类法律文件&#xf…

Mysql的sql优化

一.查询优化 我们都知道&#xff0c;在建立索引的时候&#xff0c;要考虑where后面的查询条件字段、order by 排序后面的字段 、group by 分组排序后面的字段&#xff0c;对他们的字段建立合适的索引&#xff0c;但是我们需要思考怎么建立合适的索引&#xff0c;或者建立索引之…

计算机网络-华为无线网络配置

前面已经大致了解了无线通信的原理和无线组网的概念&#xff0c;今天来学习无线的配置过程与步骤。 一、无线组网配置流程 在开始配置前复习下前面讲过无线组网有涉及几个设备&#xff0c;AC无线控制器、AP无线接入点、POE交换机。无线组网与有线组网是相对独立的&#xff0c;不…

10:LED点阵显示汉字

LED点阵显示汉字 1、字模2、横向取模 1、字模 (1)如何记录组成字的LED点阵亮灭信息&#xff08;16x16点阵一共有256点&#xff0c;显示一个特定的字需要其中有些点亮而另一些不亮&#xff0c;如何记录哪些点亮哪些点不亮&#xff1f;用字模)字模如何工作&#xff1f;256个点用…

机器学习 | 揭示EM算法和马尔可夫链的实际应用

目录 初识EM算法 马尔可夫链 HMM模型基础 HMM模型使用 初识EM算法 EM算法是一种求解含有隐变量的概率模型参数的迭代算法。该算法通过交替进行两个步骤&#xff1a;E步骤和M步骤&#xff0c;从而不断逼近模型的最优参数值。EM算法也称期望最大化算法&#xff0c;它是一个基…

负重20kg复合翼垂直起降无人机应用,复合翼无人机技术分析

主要任务应用 1.管线巡查 挂载可见光/红外二合一光电载荷和小型SAR设备&#xff0c;对既定线路进行昼夜巡视侦察&#xff0c;利用图像实时传回指挥控制中心&#xff0c;可用于石油管路、电力线路、舰艇航线及周围态势感知&#xff0c;利于依据现场实情进行战略决策和指令传达…

车载网络测试 - 总线基础 - CAN总线负载计算

我想做过CAN总线测试的都有遇到过拉高总线负载相关的测试&#xff0c;这个时候我们一般都会通过增加报文的数量或者减小报文的周期来实现&#xff0c;但是CAN总线上的负载到底是如何计算的呢&#xff1f;我想很多人都会有这个疑问吧&#xff0c;那么今天我们一起来看下如何计算…

10. Springboot集成Dubbo3(一)简单介绍

目录 1、前言 2、Dubbo3 2.1、什么是Dubbo3 2.2、Dubbo2 & Dubbo3 2.2.1、服务发现模型 2.2.2、RPC通信协议 2.2.2.1、Triple 协议 2.2.2.2、小结 2.2.3、云原生 2.2.4、maven依赖 2.2.5、性能 3、小结 1、前言 Dubbo是一个开源的Java分布式服务框架&#xff…

ProtonMail邮箱怎么样?国内有什么替代品?

ProtonMail作为业界知名的加密邮箱提供者&#xff0c;其安全性、隐私保护等特性让不少追求私密通信的用户趋之若鹜。然而对于国内用户而言&#xff0c;ProtonMail可能并非最佳选择&#xff0c;受限于许多因素&#xff0c;从语言支持到服务器位置再到可访问性&#xff0c;都可能…

个人博客说明

本人博客主要发布平台为博客园 https://www.cnblogs.com/carmi 更多详细&#xff0c;完整图片的文章还请师傅们动动小手到博客园去看吧。

泰克示波器——TBS2000系列界面整体介绍

目录 1.1 通道区域面板标识1.2 示波器测试输出&#xff08;检测探针与设置的好坏&#xff09;1.3 面板其他快捷按钮1.4 波器整体界面 1.1 通道区域面板标识 在通道面板的下方标识有示波器的通道属性以及参数值&#xff0c;如我使用的型号为“TBS2104X”的示波器&#xff0c;面…

【C#】.net core 6.0 设置根目录下某个文件夹可访问,访问创建的图片等资源

欢迎来到《小5讲堂》 大家好&#xff0c;我是全栈小5。 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点的理解和掌握。…