LeetCode笔记:167. Two Sum II - Input array is sorted
问题:
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
大意:
给出一个递增排好序的整型数组,找出两个数组相加等于目标数字。 函数 twoSum 应该返回两个数字的索引,index1 必须小于 index2。请注意你返回的结果(index1 和 index2)不是基于0开始的。 你可以假设每个输入都有一个结果。 输入:numbers={2, 7, 11, 15}, target=9 输出:index1=1, index2=2
思路:
最直接的方法是遍历每一个数,然后看它后面的每个数与它相加能不能等于目标数字,但是这样太慢了。
要利用好数组已经排好序的条件,两个数相加一定是一大一小相加得出目标数字,那么我们可以用两个游标,一个从数组头开始遍历,一个从数组尾开始遍历,如果数组头的数字小于目标数字减去数组尾的数字,则数组头的游标往后移动一格,否则数组尾的游标往前移动一格。如果两个数字相加正好等于目标数字,那么结束循环将结果返回,注意索引要求从1开始,所以我们要将得出得的两个索引号都加一。
举个例子,数组为 [1,2,3,4],目标数字为6,i 和 j 分别一开始在1和4两个数字,因为1小于6-4,所以数组头的游标指向2,数组尾的游标不变,此时2+4正好等于6,返回结果索引为2和4,而不是1和3。
代码(Java):
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
int i = 0;
int j = numbers.length-1;
while (i < j) {
if (numbers[i] + numbers[j] == target) {
result[0] = i+1;
result[1] = j+1;
break;
}
if (numbers[i] < target - numbers[j]) i++;
else j--;
}
return result;
}
}
相关文章
- 8P升完iOS14.5准正式版后“重生”,说说我的真实体验
- ubantu18.04下Hadoop安装与伪分布式配置
- appium 遇到的坑
- 谷歌启动 Android 12 的下一个开发者预览版
- 谷歌放大招!安卓12预览版最后一次更新,2021年8月或问世
- iOS 有哪些迷惑的设计规范?
- iOS系统即将迎来升级,新功能备受欢迎,安卓用户只能干看着
- iOS15新功能来袭,让人惊喜让人忧,你们期待吗?
- 安卓8GB运存都表示卡顿了,为何苹果手机才4GB却一点不着急
- 谷歌大脑创始成员辞职,他也和Jeff Dean闹掰了
- 交互优化方案的流程是什么样的?来看高手的总结!
- B端设计师怎样发挥设计价值?来看京东高手的总结!
- Android 12现在有了设备搜索API 可用于第三方启动程序
- 10 年版权案终了结:美最高法院裁定谷歌安卓系统未侵权甲骨文 Java
- 谷歌地图大更新!AR导航转室内,机场商场不再难逛
- 苹果iOS系统隐藏的6个实用功能,不会用真是太浪费了
- iOS 14.5不再默认为女性语音 英语Siri新增两种声音
- 支付宝收钱码提现免费服务再延长 3 年,且不设单笔上限和单日上限
- 手机内存怎么删?这三种方式都可以实现,根据需求选择即可
- 图数据挖掘:小世界网络模型和分散式搜索