使用哈希表的任务示例

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 中未找到该元素，则添加到 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 中，向 pairs 列表中添加配对 (complement, num)。
• 将当前数字添加到 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)]

如你所见，朴素解法需要两个嵌套循环，这使得它在处理大数组时效率低下。使用哈希表的解法能更快地达到相同目的。