前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >前端算法专栏-数组-167. 两数之和 II - 输入有序数组

前端算法专栏-数组-167. 两数之和 II - 输入有序数组

原创
作者头像
程序员库里
发布2023-12-06 09:37:34
1370
发布2023-12-06 09:37:34
举报
文章被收录于专栏:全栈学习全栈学习

介绍

Hi 大家好。我是程序员库里,今天新开一个前端算法专栏。

接下来会分类给大家分享常考算法题目。

很多朋友也是看着这套系列算法拿到很多offer!所以也是想分享给更多朋友,帮助到有需要的朋友。

分类

数组-对撞指针

题目

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 **非递减顺序排列  ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 index2

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1:

示例 2:

示例 3:

解释

  1. 采用对撞指针的方法,利用数组是升序的。
  2. 定义一个变量left,初始值是0,指向数组第一个位置,表示左指针
  3. 定义一个变量right,初始值是 numbers.length-1,指向数组最后一个位置,表示右指针
  4. 开始进行循环,条件是当left小于right的时候
  5. 当 左指针指向的元素加上右指针指向的元素刚好等于目标值, 此时表明找到了这两个元素,因为题目要求是索引从1开始,所以返回left+1, right+1
  6. 当 左指针指向的元素加上右指针指向的元素 小于 目标值,因为数组是升序的,所以需要将左指针向右移动一位,才有可能使得左指针指向的元素加上右指针指向的元素 等于 目标值,即 left++
  7. 当 左指针指向的元素加上右指针指向的元素 大于 目标值,因为数组是升序的,所以需要将右指针向左移动一位,才有可能使得左指针指向的元素加上右指针指向的元素 等于 目标值,即 right--
  8. 当遍历完之后,因为题目要求是有解的,所以最后返回 left+1, right+1

代码

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 介绍
  • 分类
  • 题目
  • 解释
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档