面试算法6:排序数组中的两个数字之和
题目
输入一个递增排序的数组和一个值k,请问如何在数组中找出两个和为k的数字并返回它们的下标?假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次。例如,输入数组[1,2,4,6,10],k的值为8,数组中的数字2与6的和为8,它们的下标分别为1与3。
分析
存在时间复杂度是O(n)、空间复杂度是O(1)的解法。我们用两个指针P1和P2分别指向数组中的两个数字。指针P1初始化指向数组的第1个(下标为0)数字,指针P2初始化指向数组的最后一个数字。如果指针P1和P2指向的两个数字之和等于输入的k,那么就找到了符合条件的两个数字。如果指针P1和P2指向的两个数字之和小于k,那么我们希望两个数字的和再大一点。由于数组已经排好序,因此可以考虑把指针P1向右移动。因为在排序数组中右边的数字要大一些,所以两个数字的和也要大一些,这样就有可能等于输入的数字k。同样,当两个数字的和大于输入的数字k时,可以把指针P2向左移动,因为在排序数组中左边的数字要小一些。
解
public class Test {public static void main(String[] args) {int[] nums = {1, 2, 4, 6, 10};int[] result = towSum(nums, 8);for (int res : result) {System.out.println(res);}}public static int[] towSum(int[] numbers, int target) {int i = 0;int j = numbers.length - 1;while (i < j && numbers[i] + numbers[j] != target) {if (numbers[i] + numbers[j] < target) {i++;}else {j--;}}return new int[] {i, j};}
}
相关文章:
面试算法6:排序数组中的两个数字之和
题目 输入一个递增排序的数组和一个值k,请问如何在数组中找出两个和为k的数字并返回它们的下标?假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次。例如,输入数组[1,2,4,6&…...
【智能家居-大模型】构建未来,聆思大模型智能家居交互解决方案正式发布
LISTENAI 近日,国内11家大模型陆续通过《生成式人工智能服务管理暂行办法》备案,多家大模型产品已正式开放,激发了新一轮大模型热潮。大模型在自然语言理解方面的巨大突破,实现了认知智能的技术跃迁,带来了时代的智慧…...
通讯网关软件002——利用CommGate X2HTTP-U实现HTTP访问OPC UA Server
本文介绍利用CommGate X2HTTP-U实现HTTP访问OPC UA Server。CommGate X2HTTP是宁波科安网信开发的网关软件,软件可以登录到网信智汇(wangxinzhihui.com)下载。 【案例】如下图所示,实现上位机通过HTTP来获取OPC UA Server的数据。 【解决方案】设置网关机…...
模拟经营类游戏是怎么开发的?
模拟经营类游戏开发是一个充满挑战但也充满乐趣的领域。下面是一些步骤和关键考虑因素,可以帮助您开始开发自己的模拟经营游戏: 明确游戏概念: 确定游戏开发的主题和类型,例如城市建设、农场经营、餐厅经营等。 制定一个引人入胜…...
基于JAVA+SSM+微信小程序+MySql的图书捐赠管理系统设计与实现
✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目背景介绍: 在当今社会࿰…...
软件设计模式系列之六——单例模式
1 模式的定义 单例模式(Singleton Pattern)是一种常见的创建型设计模式,其主要目的是确保一个类只有一个实例,并提供一个全局访问点来获取该实例。这意味着无论何时何地,只要需要该类的实例,都会返回同一个…...
verdi dump状态机的波形时直接显示状态名
前段时间看到别人用verdi看状态机的波形时,可以显示定义的状态参数,觉得很有意思,特地学习了一下 通常拉出状态机信号的波形是下面这样的 这种信号,我们要想知道每个数值代表的状态,还需要跟定义的parameter比对 像这…...
代码随想录算法训练营19期第53天
1143.最长公共子序列 视频讲解:动态规划子序列问题经典题目 | LeetCode:1143.最长公共子序列_哔哩哔哩_bilibili 代码随想录 初步思路:动态规划。 总结: dp[i][j] :长度为[0, i - 1]的字符串A与长度为[0, j - 1]…...
二刷力扣--栈和队列
栈和队列 栈和队列基础(Python) 栈一种先进后出,队列先进后出。 Python中可以用list实现栈,用append()模拟入栈,用pop()模拟出栈。 也可以用list实现队列,但是效率较低,一般用collections.deq…...
第六章 图 十、关键路径
开始顶点(源点): 在AOE网中仅有一个入度为0的顶点,称为开始顶点(源点),它表示整个工程的开始; 结束顶点(汇点): 也仅有一个出度为0的顶点,称为结束顶点(汇点)…...
Virtualbox固定存储硬盘转换为动态存储硬盘
现象 一开始分配固定存储过大,占了太多空间,现在想换成动态存储释放空闲空间。 解决 关闭虚拟机进入虚拟介质管理从使用的硬盘复制出一个动态存储硬盘在设置中把硬盘替换为副本硬盘 详细步骤参考: https://blog.csdn.net/qq_24033983/arti…...
【栈与队列面试题】有效的括号(动图演示)
leetcode20.括号匹配问题 前言: 💥🎈个人主页:Dream_Chaser~ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上栈与队列的面试OJ题目 目录 leetcode20.括号匹配问题 1.问题描…...
基于matlab实现的弹簧振动系统模型程序(动态模型)
完整代码: clear all; %System data m1.0; zeta0.01; omega01.0; Dt1.0; f01.0; x00.0; dotx00.0; xmaxsqrt(x0^2(dotx0/omega0)^2)min([0.5*abs(f0)*Dt/(m*omega0) f0/omega0^2]); omegadomega0*sqrt(1-zeta^2); dt00.1*pi/omega0; nstep500; a0.70; b0.…...
哨兵1号(Sentinel-1)SAR卫星介绍
1. 哥白尼计划 说起欧空局的哨兵1号,就不得不先说一下欧空局的“哥白尼计划”。 欧空局的哥白尼计划(Copernicus Programme)是欧空局与欧盟合作的一项极其重要的地球观测计划。该计划旨在提供免费开放的、可持续的地球观测数据,…...
[maven] scopes 管理 profile 测试覆盖率
[maven] scopes & 管理 & profile & 测试覆盖率 这里将一些其他的特性和测试覆盖率(主要是 jacoco) scopes maven 的 scope 主要就是用来限制和管理依赖的传递性,简单的说就是,每一个 scope 都有其对应的特性&…...
css网页打印字体设置
media print {font-family:"SimHei";color: #000;border-color: #000; }常用字符编码表 中文名英文名Unicode 编码黑体SimHeiSimHei微软雅黑Microsoft YaHei5FAE\8F6F\96C5\9ED1宋体SimSun\5B8B\4F53仿宋FangSong\4EFF\5B8B html5常用转义字符℃ 字符十…...
JAVA高级技术入门(单元测试,反射,注解,动态代理)
JAVA高级技术入门(单元测试,反射,注解,动态代理) 一、Junit单元测试二、反射1.认识反射,获取类概念:快速入门:获取Class对象的三种方式 2.1获取类的构造器2.2获取类的构造器的作用&a…...
uni-app 实现自定义按 A~Z 排序的通讯录(字母索引导航)
创建 convertPinyin.js 文件 convertPinyin.js 将下面的内容复制粘贴到其中 const pinyin (function() {let Pinyin function(ops) {this.initialize(ops);},options {checkPolyphone: false,charcase: "default"};Pinyin.fn Pinyin.prototype {init: functi…...
C++ PrimerPlus 复习 第一章 命令编译链接文件 make文件
第一章 命令编译链接文件 C 有什么呢?C 源代码文件后缀运行C过程可执行代码:编译语法:makeMakefile 基础语法编写完make只要和将要编译的文件放一起就行 然后在该目录使用make命令,就将自动运行;基础的Makefile版本 现…...
微信小程序——常用组件的属性介绍
常用的组件内容标签 text 文本组件类似于HTML中的span标签,是一个行内元素rich-text 富文本标签支持把HTML字符串渲染为WXML结构 text标签的基本使用 通过text组件的selectable属性,实现长按选中文本内容的效果。只有text标签支持长按选中效果&#x…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
