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

# 0167. 两数之和 II \* 输入有序数组 ## 题目地址(167. 两数之和 II - 输入有序数组) <https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/> ## 题目描述这是leetcode头号题目`two sum`的第二个版本，难度简单。 ``` <pre class="calibre18">``` 给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 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: ``` <pre class="calibre18">``` /** * @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: ``` <pre class="calibre18">``` class Solution { public: vector<int> twoSum(vector<int>& 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: ``` <pre class="calibre18">``` 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: ``` <pre class="calibre18">``` 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(N)O(N) - 空间复杂度：O(1)O(1)O(1) 更多题解可以访问我的LeetCode题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经30K star啦。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)