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

分享
藏宝库编辑 2024-9-17 22:48:35 33 0 来自 中国
1.标题

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减次序分列  ,请你从数组中找出满意相加之和即是目的数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的情势返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复利用相同的元素。
你所计划的办理方案必须只利用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
表明:2 与 7 之和即是目的数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
表明:2 与 4 之和即是目的数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:
输入:numbers = [-1,0], target = -1
输出:[1,2]
表明:-1 与 0 之和即是目的数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示:
2 <= numbers.length <= 3 * 104
-1000 <= numbers <= 1000
numbers 按 非递减次序 分列
-1000 <= target <= 1000
仅存在一个有用答案
2.双指针

初始时两个指针分别指向第一个元素位置和末了一个元素的位置。每次盘算两个指针指向的两个元素之和,
并和目的值比力。如果两个元素之和即是目的值,则发现了唯一解。如果两个元素之和小于目的值,
则将左侧指针右移一位。如果两个元素之和大于目的值,则将右侧指针左移一位。移动指针之后,重复上述利用,直到找到答案。
利用双指针的实质是缩小查找范围。那么会不会把大概的解过滤掉?答案是不会。
由于标题确保有唯一的答案,因此利用双指针肯定可以找到答案。
3.代码
您需要登录后才可以回帖 登录 | 立即注册

Powered by CangBaoKu v1.0 小黑屋藏宝库It社区( 冀ICP备14008649号 )

GMT+8, 2024-10-19 04:22, Processed in 0.193316 second(s), 32 queries.© 2003-2025 cbk Team.

快速回复 返回顶部 返回列表