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

題目

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

三種解法

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

Two Pointers 類型整理

類型	移動方式 (關鍵邏輯)	核心目的 (解決的問題)	範例題
Opposite Direction	兩端向中間收斂，每次依條件只動一邊。	在有序數組中，高效尋找配對或縮小搜索空間。	Two Sum II、Valid Palindrome
Fast-Slow	不同步推進（快慢速度），用於拉開距離。	檢測鏈表/數組中的循環、尋找中點，或原地去重。	Linked List Cycle、Remove Duplicates from Sorted Array
Sliding Window	擴展右邊界，收縮左邊界，維持窗口內的條件。	搜尋滿足特定條件的子範圍（子數組/子字串）的最大/最小問題。	Longest Substring Without Repeating Characters、Minimum Size Subarray Sum
Two Sequences Sync	兩個指標獨立或同步地推進，同時比較兩個序列。	合併或比對差異兩個有序的序列。	Merge Two Sorted Lists、Compare Version Numbers
K-Distance Window	右指標擴展，左指標受限於 $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