# 0167. 两数之和 II 输入有序数组
### 题目地址(167. 两数之和 II - 输入有序数组)
### 题目描述
这是 leetcode 头号题目`two sum`的第二个版本，难度简单。
```
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
```
### 前置知识
* 双指针
### 公司
* 阿里
* 腾讯
* 百度
* 字节
* amazon
### 思路
由于题目没有对空间复杂度有求，用一个 hashmap 存储已经访问过的数字即可。
假如题目空间复杂度有要求，由于数组是有序的，只需要双指针即可。一个 left 指针，一个 right 指针， 如果 left + right 值 大于 target 则 right 左移动， 否则 left 右移，代码见下方 python code。
> 如果数组无序，需要先排序（从这里也可以看出排序是多么重要的操作）
### 关键点解析
* 由于是有序的，因此双指针更好
### 代码
* 语言支持：JS，C++，Java，Python
Javascript Code:
```js
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
const visited = {}; // 记录出现的数字， 空间复杂度N
for (let index = 0; index < numbers.length; index++) {
const element = numbers[index];
if (visited[target - element] !== void 0) {
return [visited[target - element], index + 1];
}
visited[element] = index + 1;
}
return [];
};
```
C++ Code:
```
class Solution {
public:
vector twoSum(vector& numbers, int target) {
int n = numbers.size();
int left = 0;
int right = n-1;
while(left <= right)
{
if(numbers[left] + numbers[right] == target)
{
return {left + 1, right + 1};
}
else if (numbers[left] + numbers[right] > target)
{
right--;
}
else
{
left++;
}
}
return {-1, -1};
}
};
```
Java Code:
```java
class Solution {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int left = 0;
int right = n-1;
while(left <= right)
{
if(numbers[left] + numbers[right] == target)
{
return new int[]{left + 1, right + 1};
}
else if (numbers[left] + numbers[right] > target)
{
right--;
}
else
{
left++;
}
}
return new int[]{-1, -1};
}
}
```
Python Code:
```python
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
visited = {}
for index, number in enumerate(numbers):
if target - number in visited:
return [visited[target-number], index+1]
else:
visited[number] = index + 1
# 双指针思路实现
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] < target:
left += 1
if numbers[left] + numbers[right] > target:
right -= 1
if numbers[left] + numbers[right] == target:
return [left+1, right+1]
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 30K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/167.two-sum-ii-input-array-is-sorted.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.