0167. 两数之和 II 输入有序数组

题目地址(167. 两数之和 II - 输入有序数组)

题目描述

这是 leetcode 头号题目two sum的第二个版本,难度简单。
1
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
2
3
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
4
5
说明:
6
7
返回的下标值(index1 和 index2)不是从零开始的。
8
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
9
示例:
10
11
输入: numbers = [2, 7, 11, 15], target = 9
12
输出: [1,2]
13
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
Copied!

前置知识

  • 双指针

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • amazon

思路

由于题目没有对空间复杂度有求,用一个 hashmap 存储已经访问过的数字即可。
假如题目空间复杂度有要求,由于数组是有序的,只需要双指针即可。一个 left 指针,一个 right 指针, 如果 left + right 值 大于 target 则 right 左移动, 否则 left 右移,代码见下方 python code。
如果数组无序,需要先排序(从这里也可以看出排序是多么重要的操作)

关键点解析

  • 由于是有序的,因此双指针更好

代码

  • 语言支持:JS,C++,Java,Python
Javascript Code:
1
/**
2
* @param {number[]} numbers
3
* @param {number} target
4
* @return {number[]}
5
*/
6
var twoSum = function (numbers, target) {
7
const visited = {}; // 记录出现的数字, 空间复杂度N
8
9
for (let index = 0; index < numbers.length; index++) {
10
const element = numbers[index];
11
if (visited[target - element] !== void 0) {
12
return [visited[target - element], index + 1];
13
}
14
visited[element] = index + 1;
15
}
16
return [];
17
};
Copied!
C++ Code:
1
class Solution {
2
public:
3
vector<int> twoSum(vector<int>& numbers, int target) {
4
int n = numbers.size();
5
int left = 0;
6
int right = n-1;
7
while(left <= right)
8
{
9
if(numbers[left] + numbers[right] == target)
10
{
11
return {left + 1, right + 1};
12
}
13
else if (numbers[left] + numbers[right] > target)
14
{
15
right--;
16
}
17
else
18
{
19
left++;
20
}
21
}
22
return {-1, -1};
23
}
24
};
Copied!
Java Code:
1
class Solution {
2
public int[] twoSum(int[] numbers, int target) {
3
int n = numbers.length;
4
int left = 0;
5
int right = n-1;
6
while(left <= right)
7
{
8
if(numbers[left] + numbers[right] == target)
9
{
10
return new int[]{left + 1, right + 1};
11
}
12
else if (numbers[left] + numbers[right] > target)
13
{
14
right--;
15
}
16
else
17
{
18
left++;
19
}
20
}
21
22
return new int[]{-1, -1};
23
}
24
}
Copied!
Python Code:
1
class Solution:
2
def twoSum(self, numbers: List[int], target: int) -> List[int]:
3
visited = {}
4
for index, number in enumerate(numbers):
5
if target - number in visited:
6
return [visited[target-number], index+1]
7
else:
8
visited[number] = index + 1
9
10
# 双指针思路实现
11
class Solution:
12
def twoSum(self, numbers: List[int], target: int) -> List[int]:
13
left, right = 0, len(numbers) - 1
14
while left < right:
15
if numbers[left] + numbers[right] < target:
16
left += 1
17
if numbers[left] + numbers[right] > target:
18
right -= 1
19
if numbers[left] + numbers[right] == target:
20
return [left+1, right+1]
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。