友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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.
Note:
-
Your returned answers (both index1 and index2) are not zero-based.
-
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
思路分析
利用输入数组的有序性，可以从两边向中级"挤压"来查找正确解。
-
一刷
-
二刷
-
三刷
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};
}