題目

給定一個整數陣列 numbers 和一個目標數字 target，請找出 numbers 中兩個數字的和等於 target，並返回它們的索引。假設每個輸入只會有一個解，並且你可以假設每個輸入的數字都是唯一的。

三種解法

這題跟 Two Sum 最大的差別是，這邊 INPUT: 的 numbers 陣列是 sorted 的，所以題目會提示我們用更有效率的解法

雙指標（Two Pointers）類型總整理

類型	初始化	移動方式	常見用途	範例題
對撞指標 (Opposite Direction)	left = 0, right = n-1	每次依條件只動一邊	在排序好的 array 裡找條件配對、縮小搜尋範圍	Two Sum II、Valid Palindrome、Trapping Rain Water
同向指標 / 快慢指標 (Same Direction / Fast-Slow)	slow = 0, fast = 0	fast 每次走一步或多步，slow 慢一些	檢測循環、找中點、移除重複	Linked List Cycle、Remove Duplicates from Sorted Array
滑動視窗 (Sliding Window)	left = 0，right 迴圈遍歷	擴展右邊界、必要時收縮左邊界	子陣列/子字串搜尋、最大最小範圍問題	Longest Substring Without Repeating Characters、Minimum Size Subarray Sum
雙序列同步 (Two Sequences Sync)	i, j = 0, 0	同時比較兩個排序好的陣列或字串	合併排序、比對差異	Merge Two Sorted Lists、Compare Version Numbers
K 距離內移動窗口	left, right = 0, 0	視窗長度受限於 K	滿足「距離 ≤ K」的條件判斷	Contains Duplicate II、Longest Repeating Character Replacement

兩指針法（Two Pointer）

這邊是用 Two Pointer 的對撞指標 (Opposite Direction)，時間複雜度為 O(n)。該方法的思路是將 numbers 陣列排序後，使用兩個指針分別指向陣列的開頭和結尾，然後不斷根據當前指針所指的數字來調整指針的位置。

# Two Pointer
left, right = 0, len(numbers) - 1
while left < right:
    total = numbers[left] + numbers[right]
    if total < target:
        left += 1
    elif total > target:
        right -= 1
    else:
        return [left + 1, right + 1]
return []  # 沒有結果

時間與空間複雜度：

TC：O(n)
SC：O(1)

Brute Force

# O(n^2) Brute Force
for i in range(len(numbers)):
    for j in range(i + 1, len(numbers)):
        if numbers[j] == target - numbers[i]:
            return [i + 1, j + 1]

時間與空間複雜度：

TC：O(n^2)
SC：O(1)

Hash Map

跟 Two Sum 一樣，使用 Hash Map 儲存已經遍歷過的數字和它們的索引。

# O(n), SC: O(n) Hash map
hash_m = {}
for i, num in enumerate(numbers, start=1):
    diff = target - num
    if diff in hash_m:
        return [hash_m[diff], i]
    hash_m[num] = i

時間與空間複雜度：

TC：O(n)
SC：O(n)

若您覺得這篇文章對您有幫助，歡迎分享出去讓更多人看到⊂◉‿◉つ~

LeetCode 獨自升級紀 - [Two Pointer] Two Integer Sum II (Medium)

題目

三種解法

雙指標（Two Pointers）類型總整理

兩指針法（Two Pointer）

Brute Force

Hash Map

留言版

FEATURED TAGS

FRIENDS