使用雜湊表的練習問題

8.1 在陣列中尋找重複元素的問題

問題：給定一個數字陣列。需要找出並返回所有的重複數字。

解決方案： 使用雜湊表來追踪已經出現過的數字。如果一個數字再次出現，將其添加到重複列表中。

實現範例：

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用範例
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # 輸出: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # 輸出: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # 輸出: []

說明：

• 創建一個空集合 seen 來追踪唯一數字。
• 遍歷陣列中的每個元素。如果元素已在 seen 中，將其添加到 duplicates 列表中。
• 如果元素不在 seen 中，就把它添加進去。
• 返回重複列表。

注意，該函數可正確處理空陣列和不含重複項的陣列，在這兩種情況下會返回一個空列表。

8.2 檢查字母重組的問題

問題： 給定兩個字符串。需要判斷它們是否為字母重組(包含相同數量的相同字符)。

解決方案： 使用雜湊表來計算兩個字符串中字母的出現頻率並比較結果。

實現範例：

def are_anagrams(str1, str2):
    # 將字符串轉為小寫以考慮不同的字母大小寫
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # 計算第一個字符串中字母出現的頻率
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # 減去第二個字符串中字母的頻率
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # 確保字典中的所有值都為0
    return all(count == 0 for count in char_count.values())

# 使用範例
print(are_anagrams("listen", "silent"))  # 輸出: True
print(are_anagrams("hello", "world"))  # 輸出: False
print(are_anagrams("", ""))  # 輸出: True
print(are_anagrams("Tea", "Eat"))  # 輸出: True

說明：

• 如果字符串長度不同，它們不可能是字母重組。
• 使用字典 char_count 計算第一個字符串中字母的頻率。
• 遍歷第二個字符串並減去字母的頻率。
• 檢查字典中的所有值是否為零。如果是，則字符串為字母重組。

注意，該函數考慮了字母大小寫，將兩個字符串轉為小寫後再進行比較。它還能正確處理空字符串，視其為彼此的字母重組。

8.3 尋找給定總和的數字對問題

問題： 給定一個數字陣列和一個目標總和值。需要找出所有和為目標值的數字對。

解決方案： 使用雜湊表來儲存數字並檢查它們是否能與當前數字組成給定總和的配對。

實現範例：

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []
    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)
    return pairs

# 使用範例
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 輸出: [(1, 5), (1, 5)]

說明：

• 創建一個空集合 seen 來追踪數字。
• 對於陣列中的每個數字，計算它的補數 complement（即目標總和減去當前數字）。
• 如果補數已在 seen 中，將配對 (complement, num) 添加到 pairs 列表中。
• 將當前數字添加到 seen 中。
• 返回配對列表。

重要的是，這個算法的時間複雜度為 O(n)，其中 n 是陣列中的元素數量。這比簡單的雙重循環解法的 O(n^2) 時間複雜度要效率高得多。使用雜湊表讓我們在一次遍歷陣列中找到所有配對，這在處理大數據量時特別重要。

作對比，這是簡單解法的 O(n^2) 時間複雜度樣子：

def find_pairs_naive(arr, target_sum):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# 使用範例
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # 輸出: [(1, 5), (1, 5)]

如你所見，簡單解法需要兩個嵌套循環，這使得它在處理大型陣列時效率低下。使用雜湊表的解法能更快達到相同目的。