题目

题目：给定一个整数列表 nums 和一个整数 target，请使用哈希表找出列表中两个数的下标，使得这两个数之和等于 target。假设每个输入都有且仅有一个解决方案，且不能使用同一个元素两次。

示例：

输入：

nums = [2, 7, 11, 15]
target = 9

输出：

[0, 1]

解释：因为 nums[0] + nums[1] = 2 + 7 = 9，所以答案是 [0, 1]。
请实现一个函数 two_sum，接收 nums 和 target 作为输入参数，返回满足条件的下标列表。

def two_sum(nums, target):
    # 在这里编写您的代码
    pass

提示：考虑使用字典（Python 中的哈希表实现）来存储已经遍历过的元素及其下标。这样，在遍历列表时，可以快速查找哈希表中是否存在一个值，使得当前元素和这个值之和等于 target。

答案

def two_sum(nums, target):
    hash_table = {}  # 创建一个空字典用于存储已遍历过的元素及其下标
    
    for i, num in enumerate(nums):  # 遍历整数列表及其下标
        complement = target - num  # 计算目标值与当前元素的差值
        
        # 检查差值是否已经在哈希表中
        if complement in hash_table:
            # 如果找到了匹配的组合，返回差值的下标和当前元素的下标
            return [hash_table[complement], i]
        
        # 如果差值不在哈希表中，将当前元素及其下标添加到哈希表
        hash_table[num] = i
        
    return None  # 如果没有找到匹配的组合，返回 None

现在我们可以测试这个函数：

nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)  # 输出: [0, 1]

在这个实现中，我们遍历输入的整数列表 nums。对于每一个元素 num，我们计算 target 减去 num 的差值 complement。
然后，我们检查哈希表 hash_table 是否已经包含了这个差值。如果包含，说明我们找到了一个匹配的组合，返回差值的下标和当前元素的下标。如果不包含，我们将当前元素 num 及其下标 i 添加到哈希表中。这样，在遍历过程中，我们可以快速地查找哈希表中是否存在满足条件的值。
下面是带留学生实现的字典，如何解决这道题目呢？

# Python 实现二次探测，需要如下内容：
# 1. 原理解析
# 2. 特点
# 3. 实现代码
# 4. 代码详细注释
# 5. 代码测试
# 6. 应用场景

"""
二次探测（Quadratic Probing）是一种开放寻址法（Open Addressing）的哈希表（Hash Table）解决冲突的方法。
当插入一个新的键值对时，如果发生冲突，二次探测会沿着二次探测序列查找下一个可用的哈希表索引。
具体地说，当第 i 次冲突发生时，二次探测会尝试在 (hash(key) + i^2) % table_size 的位置进行插入或查找。

特点：
二次探测可以解决哈希表的冲突问题
对于较小的负载因子，二次探测性能较好
相比于线性探测，二次探测可以更好的避免聚簇现象
"""

class QuadraticProbingHashTable:
    def __init__(self, size=11):
        self.size = size  # 设置哈希表大小
        self.slots = [None] * self.size  # 初始化哈希表的键槽
        self.data = [None] * self.size  # 初始化哈希表的值槽

    def put(self, key, value):
        hash_value = self.hash_function(key)  # 计算键的哈希值

        # 如果槽为空，插入键值对
        if self.slots[hash_value] is None:
            self.slots[hash_value] = key
            self.data[hash_value] = value
        else:
            # 如果槽已被占用，且键相同，则更新值
            if self.slots[hash_value] == key:
                self.data[hash_value] = value
            else:
                # 如果槽已被占用，键不同，则进行二次探测
                i = 1
                next_slot = self.rehash(hash_value, i)
                while self.slots[next_slot] is not None and self.slots[next_slot] != key:
                    i += 1
                    next_slot = self.rehash(hash_value, i)

                # 如果找到空槽或者相同的键，则插入或更新键值对
                if self.slots[next_slot] is None:
                    self.slots[next_slot] = key
                    self.data[next_slot] = value
                else:
                    self.data[next_slot] = value

    def hash_function(self, key):
        return key % self.size  # 计算哈希值的简单方法

    def rehash(self, old_hash, i):
        return (old_hash + i ** 2) % self.size  # 二次探测的哈希重新计算

    def get(self, key):
        start_slot = self.hash_function(key)  # 计算键的哈希值
        position = start_slot
        found = False
        stop = False
        i = 1

        # 遍历哈希表，直到找到键或遍历完所有槽
        while self.slots[position] is not None and not found and not stop:
            if self.slots[position] == key:  # 如果找到键，返回对应的值
                found = True
                return self.data[position]
            else:
                position = self.rehash(start_slot, i)  # 二次探测寻找下一个槽
                i += 1
                if position == start_slot:  # 如果回到起始槽，停止遍历
                    stop = True

        return None  # 如果未找到键，返回 None

    # 重载字典访问和赋值操作符
    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        self.put(key, value)


ht = QuadraticProbingHashTable()
ht[54] = "cat"
ht[26] = "dog"
ht[93] = "lion"
ht[17] = "tiger"
ht[77] = "bird"
ht[31] = "cow"
ht[44] = "goat"
ht[55] = "pig"
ht[20] = "chicken"

# 输出哈希表的键槽和值槽
print("Slots: ", ht.slots)
print("Data: ", ht.data)

# 从哈希表中获取键对应的值
print("Value for key 20: ", ht[20])  # 输出: Value for key 20:  chicken

# 更新哈希表中的键值对
ht[20] = "duck"

# 输出更新后的哈希表的键槽和值槽
print("Updated slots: ", ht.slots)
print("Updated data: ", ht.data)

# 从哈希表中获取更新后的键对应的值
print("Updated value for key 20: ", ht[20])  # 输出: Updated value for key 20:  duck

以下是使用二次探测哈希表实现的 two_sum 函数：

def two_sum(nums, target):
    hash_table = QuadraticProbingHashTable()  # 创建一个二次探测哈希表实例
    
    for i, num in enumerate(nums):  # 遍历整数列表及其下标
        complement = target - num  # 计算目标值与当前元素的差值
        
        # 检查差值是否已经在哈希表中
        if hash_table.get(complement) is not None:
            # 如果找到了匹配的组合，返回差值的下标和当前元素的下标
            return [hash_table[complement], i]
        
        # 如果差值不在哈希表中，将当前元素及其下标添加到哈希表
        hash_table[num] = i
        
    return None  # 如果没有找到匹配的组合，返回 None

这个实现与之前的实现非常相似，但是在这里我们使用 QuadraticProbingHashTable 类来代替字典。我们使用 get 方法来检查哈希表中是否存在差值 complement，如果存在，则返回差值的下标和当前元素的下标。如果不存在，我们将当前元素 num 及其下标 i 添加到哈希表中。这种实现方式同样可以在遍历过程中快速查找满足条件的值。