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 的文章