友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
167. 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index~1~] 和 numbers[index~2~] ，则 1 <= index~1~ < index~2~ <= numbers.length 。
以长度为 2 的整数数组 [index~1~, index~2~] 的形式返回这两个整数的下标 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[i] <= 1000 -
numbers按 非递减顺序 排列 -
-1000 <= target <= 1000 -
仅存在一个有效答案
思路分析
利用输入数组的有序性，可以从两边向中级"挤压"来查找正确解。
-
一刷
-
二刷
-
三刷
-
四刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum II - Input array is sorted.
* Memory Usage: 42.2 MB, less than 5.22% of Java online submissions for Two Sum II - Input array is sorted.
*
* Copy from: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leetco/[两数之和 II - 输入有序数组 - 两数之和 II - 输入有序数组 - 力扣（LeetCode）]
*/
public int[] twoSum(int[] numbers, int target) {
int low = 0, high = numbers.length - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[]{low + 1, high + 1};
} else if (sum < target) {
low++;
} else {
high--;
}
}
return new int[]{-1, -1};
}
/**
* Runtime: 4 ms, faster than 14.69% of Java online submissions for Two Sum II - Input array is sorted.
* Memory Usage: 41.8 MB, less than 5.22% of Java online submissions for Two Sum II - Input array is sorted.
*/
public int[] twoSumPair(int[] numbers, int target) {
Map<Integer, Pair> valueToIndexMap = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
valueToIndexMap.put(numbers[i], new Pair(numbers[i], i + 1));
}
for (int i = 0; i < numbers.length; i++) {
int diff = target - numbers[i];
if (valueToIndexMap.containsKey(diff)) {
Pair pair = valueToIndexMap.get(diff);
return new int[]{i + 1, pair.index};
}
}
return null;
}
private class Pair {
int value;
int index;
public Pair(int value, int index) {
this.value = value;
this.index = index;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-03 20:02:38
*/
public int[] twoSum(int[] numbers, int target) {
int low = 0, high = numbers.length - 1;
while (low < high) {
if (numbers[low] + numbers[high] == target) {
return new int[]{low + 1, high + 1};
} else if (target - numbers[low] < numbers[high]) {
high--;
} else if (numbers[low] < target - numbers[high]) {
low++;
}
}
return new int[]{-1, -1};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-13 20:20:24
*/
public int[] twoSum(int[] numbers, int target) {
int l = 0;
int r = numbers.length - 1;
while (l < r) {
int sum = numbers[l] + numbers[r];
if (sum == target) {
return new int[]{l + 1, r + 1};
} else if (sum < target) {
l++;
} else {
r--;
}
}
return new int[]{-1, -1};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-29 08:30
*/
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{left + 1, right + 1};
}