算法面试题：Python实现两数和

题目：两数之和

描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数，并返回它们的索引。假设每种输入只对应一个答案，且不能重复利用数组中同样的元素。

例如：

python
Copy code
nums = [2, 7, 11, 15]
target = 9
在这个例子中，nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]。

下面是实现题目的 Python 代码：

def two_sum(nums, target):
    # 创建一个字典用于存储已经遍历过的数字及其索引
    num_dict = {}
    
    # 遍历数组
    for i, num in enumerate(nums):
        # 计算当前数字的补数
        complement = target - num
        
        # 检查补数是否已经在字典中
        if complement in num_dict:
            # 如果找到了，返回两个数字的索引
            return [num_dict[complement], i]
        
        # 将当前数字及其索引加入字典
        num_dict[num] = i
    
    # 如果没有找到符合条件的数字，返回空列表
    return []

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

这个算法的时间复杂度是 O(n)，其中 n 是数组中元素的个数。在这个算法中，我们使用一个字典来存储已经遍历过的数字及其索引，这样可以在 O(1) 的时间内查找补数是否存在。算法遍历数组一次，所以总的时间复杂度是 O(n)。