LeetCode 两数之和题解
LeetCode 两数之和题解
题目描述
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
示例：
输入：nums = [2,7,11,15],target = 9
输出：[0,1]
解题思路
方法：哈希表
思路：
- 使用哈希表来解决这个问题。
- 遍历数组，对于每个元素，计算目标值减去当前元素的值（补数）。
- 如果补数在哈希表中，返回补数的索引和当前元素的索引。
- 如果补数不在哈希表中，将当前元素和其索引存入哈希表。
复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被访问一次。
- 空间复杂度：O(n)，需要额外的空间来存储哈希表。
代码实现
方法：哈希表
# 两数之和（哈希表） def two_sum(nums, target): hash_map = {} for i, num in enumerate(nums): complement = target - num if complement in hash_map: return [hash_map[complement], i] hash_map[num] = i return [] # 测试 def test_two_sum(): nums = [2, 7, 11, 15] target = 9 print(two_sum(nums, target)) # 输出：[0, 1] nums = [3, 2, 4] target = 6 print(two_sum(nums, target)) # 输出：[1, 2] if __name__ == "__main__": test_two_sum()测试用例
测试用例 1：基本情况
输入：nums = [2,7,11,15],target = 9
输出：[0,1]
测试用例 2：不相邻元素
输入：nums = [3,2,4],target = 6
输出：[1,2]
总结
两数之和是一个经典的哈希表问题，它可以通过哈希表来高效地解决。
哈希表法的核心思想是：遍历数组，对于每个元素，计算目标值减去当前元素的值，如果补数在哈希表中，返回结果；否则将当前元素存入哈希表。
掌握哈希表的使用方法，对于解决类似的问题非常重要。