Leetcode 167 - Two Sum II - Input Array Is Sorted

題目

Problem#

題目給你一個 1-index 的整數陣列(已排序)，問你陣列裡加起來等於 target 的兩個數字 index 為何

想法#

naive $\mathcal{O}(n^2)$ 作法會超時
掃一次，對於 index i 每次去數字的右邊($[i+1, n)$)找是否有 t - n[i] 的數字存在，二分搜加速

• 時間複雜度: $\mathcal{O}(n\log{n})$
• 空間複雜度: $\mathcal{O}(1)$

AC Code#

賞析#

• $\mathcal{O}(n)$ 的解法，用雙指標一個頭(a)一個尾(b)，假如相加比 target 小則把 a+1 (變大)；反之，相加比 target 大則把 b-1(縮小)
• $\mathcal{O}(\log{n})$ 的解法，直接一次二分搜結束，mid 直接算總和，如果大則 right - 1 如果小 left + 1