167. 兩數之和 II - 輸入有序數組（點擊查看題目）
題目描述
給定一個已按照 升序排列 的有序數組，找到兩個數使得它們相加之和等於目標數。
函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小於 index2。
說明:
- 返回的下標值（index1 和 index2）不是從零開始的。
- 你可以假設每個輸入只對應唯一的答案，而且你不可以重複使用相同的元素。
示例:
解決方案
方法 1：雙指針
算法
我們可以使用 力扣 1.兩數之和 的解法在 O(n^2) 時間 O(1) 空間暴力解決，也可以用哈希表在 O(n) 時間和 O(n) 空間內解決。然而，這兩種方法都沒有用到輸入數組已經排序的性質，我們可以做得更好。
我們使用兩個指針，初始分別位於第一個元素和最後一個元素位置，比較這兩個元素之和與目標值的大小。如果和等於目標值，我們發現了這個唯一解。如果比目標值小，我們將較小元素指針增加一。如果比目標值大，我們將較大指針減小一。移動指針後重覆上述比較知道找到答案。
假設 [...，a，b，c，...，d，e，f，...] 是已經升序排列的輸入數組，並且元素 b，e 是唯一解。因為我們從左到右移動較小指針，從右到左移動較大指針，總有某個時刻存在一個指針移動到 b 或 e 的位置。不妨假設小指針縣移動到了元素 b，這是兩個元素的和一定比目標值大，根據我們的算法，我們會向左移動較大指針直至獲得結果。
C++ 代碼實現
是否需要考慮 numbers[low] + numbers[high] 溢出呢？答案是不需要。因為即使兩個元素之和溢出了，因為只存在唯一解，所以一定會先訪問到答案。
複雜度分析
時間複雜度：O(n)。每個元素最多被訪問一次，共有 n 個元素。
空間複雜度：O(1)。只是用了兩個指針。
分享到:
閱讀更多 力扣LeetCode 的文章
