two sum 2
題目說明

給定一個已經排序好的整數陣列 numbers（從小到大），和一個目標值 target。
請回傳兩個數字的索引（1-based index），使得它們的和等於 target。
這題跟 Day 1 的 Two Sum 類似，但限制陣列已排序，所以可以用更快的雙指針法。

程式碼
Java 解法

class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1};
}
}

Python 解法

def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
elif total < target:
left += 1
else:
right -= 1

複雜度分析

• 時間複雜度：O(n)，每個元素最多被檢查一次。
• 空間複雜度：O(1)，只用到兩個指標。

心得

這題跟 Day2 相比，最大的差別是 利用陣列已排序的特性。
之前 Two Sum 用 HashMap 解需要 O(n)時間 + O(n)空間；
但這題用雙指針可以把空間壓到 O(1)，完全不需要額外結構，效率更高。
我覺得這題讓我體會到要根據題目條件調整解法，很多題目看似一樣，但限制條件不一樣，能設計出更快的演算法。