ハッシュテーブルを使った問題の例

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 アナグラムのチェック問題

問題: 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
    # 2番目の文字列の文字の頻度を減算
    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を使用します。
• 2番目の文字列を通過し、文字の頻度を減算します。
• 辞書内のすべての値がゼロであるかを確認します。もしそうなら、文字列はアナグラムです。

この関数は、大文字小文字を考慮し、比較前に両方の文字列を小文字に変換します。また、空の文字列を互いにアナグラムと見なして正しく処理します。

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に追加します。
• ペアのリストを返します。

このアルゴリズムは、配列の要素数をnとしたときにO(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)]

見て分かる通り、この素朴な方法は二重ループを必要とし、大きな配列では効率が良くありません。ハッシュテーブルを使用した解法は、同じ目的をはるかに速く達成できます。