# 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">``` <span class="hljs-title">/** * @param {number[]} numbers * @param {number} target * @return {number[]} */</span> <span class="hljs-keyword">var</span> twoSum = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">numbers, target</span>) </span>{ <span class="hljs-keyword">const</span> visited = {} <span class="hljs-title">// 記錄出現的數字， 空間復雜度N</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> index = <span class="hljs-params">0</span>; index < numbers.length; index++) { <span class="hljs-keyword">const</span> element = numbers[index]; <span class="hljs-keyword">if</span> (visited[target - element] !== <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { <span class="hljs-keyword">return</span> [visited[target - element], index + <span class="hljs-params">1</span>] } visited[element] = index + <span class="hljs-params">1</span>; } <span class="hljs-keyword">return</span> []; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>> twoSum(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& numbers, <span class="hljs-keyword">int</span> target) { <span class="hljs-keyword">int</span> n = numbers.size(); <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> right = n<span class="hljs-params">-1</span>; <span class="hljs-keyword">while</span>(left <= right) { <span class="hljs-keyword">if</span>(numbers[left] + numbers[right] == target) { <span class="hljs-keyword">return</span> {left + <span class="hljs-params">1</span>, right + <span class="hljs-params">1</span>}; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (numbers[left] + numbers[right] > target) { right--; } <span class="hljs-keyword">else</span> { left++; } } <span class="hljs-keyword">return</span> {<span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>}; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] twoSum(<span class="hljs-keyword">int</span>[] numbers, <span class="hljs-keyword">int</span> target) { <span class="hljs-keyword">int</span> n = numbers.length; <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> right = n-<span class="hljs-params">1</span>; <span class="hljs-keyword">while</span>(left <= right) { <span class="hljs-keyword">if</span>(numbers[left] + numbers[right] == target) { <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{left + <span class="hljs-params">1</span>, right + <span class="hljs-params">1</span>}; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (numbers[left] + numbers[right] > target) { right--; } <span class="hljs-keyword">else</span> { left++; } } <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{-<span class="hljs-params">1</span>, -<span class="hljs-params">1</span>}; } } ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">twoSum</span><span class="hljs-params">(self, numbers: List[int], target: int)</span> -> List[int]:</span> visited = {} <span class="hljs-keyword">for</span> index, number <span class="hljs-keyword">in</span> enumerate(numbers): <span class="hljs-keyword">if</span> target - number <span class="hljs-keyword">in</span> visited: <span class="hljs-keyword">return</span> [visited[target-number], index+<span class="hljs-params">1</span>] <span class="hljs-keyword">else</span>: visited[number] = index + <span class="hljs-params">1</span> <span class="hljs-title"># 雙指針思路實現</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">twoSum</span><span class="hljs-params">(self, numbers: List[int], target: int)</span> -> List[int]:</span> left, right = <span class="hljs-params">0</span>, len(numbers) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> left < right: <span class="hljs-keyword">if</span> numbers[left] + numbers[right] < target: left += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> numbers[left] + numbers[right] > target: right -= <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> numbers[left] + numbers[right] == target: <span class="hljs-keyword">return</span> [left+<span class="hljs-params">1</span>, right+<span class="hljs-params">1</span>] ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經30K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。