Description
給定一個已按非遞減排序的整數陣列
numbers（1-indexed），找出兩個數使它們的和等於target，回傳這兩個數的索引（1-based）。保證恰好有一組解，且不能使用同一元素兩次。
Example:
Input: numbers = [2,7,11,15], target = 9 Output: [1,2]
Intuition#
核心思路：已排序陣列，用左右指針，和太大右移左、和太小右移右，O(n) 搞定。
- 陣列已排序是關鍵條件，讓我們可以根據當前和的大小決定指針移動方向
- 若
nums[left] + nums[right] > target，右指針左移可以減小和 - 若
nums[left] + nums[right] < target，左指針右移可以增大和 - 每步都排除一個不可能的選項，不會錯過正確答案
Approaches#
1: Binary Search#
- 概念: 對每個元素
numbers[i]，用二分搜尋在剩餘部分尋找target - numbers[i] - 時間複雜度:
O(n log n)- 外層 O(n)，內層二分 O(log n) - 空間複雜度:
O(1)
class Solution {
fun twoSum(numbers: IntArray, target: Int): IntArray {
for (i in numbers.indices) {
val complement = target - numbers[i]
var lo = i + 1
var hi = numbers.size - 1
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
when {
numbers[mid] == complement -> return intArrayOf(i + 1, mid + 1)
numbers[mid] < complement -> lo = mid + 1
else -> hi = mid - 1
}
}
}
throw IllegalArgumentException("No solution found")
}
}⭐2: Two Pointers#
- 概念: 左指針從頭、右指針從尾開始，根據當前和與 target 的比較移動指針
- 時間複雜度:
O(n)- 每步至少移動一個指針，最多 n 步 - 空間複雜度:
O(1)- 只用兩個指針
class Solution {
fun twoSum(numbers: IntArray, target: Int): IntArray {
var left = 0
var right = numbers.size - 1
while (left < right) {
val sum = numbers[left] + numbers[right]
when {
sum == target -> return intArrayOf(left + 1, right + 1)
sum < target -> left++
else -> right--
}
}
throw IllegalArgumentException("No solution found")
}
}注意回傳的是 1-based 索引，別忘了 +1。另外
sum可能溢位 Int 範圍，但此題測資保證不會。
🔑 Takeaways#
- Pattern: 已排序 + 找配對 = 相向雙指針的標準場景
- 關鍵技巧: 利用排序性質，每步都能確定性地排除一側，保證不漏解且 O(n) 完成