LeetCode 1. Two Sum 题解

LeetCode 1. Two Sum 题解题目描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例 1输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2输入nums [3,2,4], target 6 输出[1,2]示例 3输入nums [3,3], target 6 输出[0,1]解题思路方法一暴力解法思路双重循环遍历数组中的每对元素检查它们的和是否等于目标值如果找到返回它们的下标复杂度分析时间复杂度O(n²)其中 n 是数组的长度。需要双重循环遍历数组。空间复杂度O(1)只需要常数级的额外空间。方法二哈希表思路使用哈希表来存储已经遍历过的元素及其下标遍历数组中的每个元素计算目标值与当前元素的差值检查差值是否在哈希表中如果在返回当前元素的下标和哈希表中差值的下标如果不在将当前元素及其下标存入哈希表复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历数组一次。空间复杂度O(n)其中 n 是数组的长度。需要使用哈希表来存储元素及其下标。代码实现方法一暴力解法class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []方法二哈希表class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: # 使用哈希表来存储已经遍历过的元素及其下标 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 []测试用例测试用例 1输入nums [2,7,11,15], target 9输出[0,1]测试用例 2输入nums [3,2,4], target 6输出[1,2]测试用例 3输入nums [3,3], target 6输出[0,1]总结本题是 LeetCode 的经典入门问题主要考察对数组遍历和哈希表的理解。两种方法各有特点暴力解法代码简洁易懂但时间复杂度较高适用于小规模数据。哈希表时间复杂度较低适用于大规模数据但需要额外的空间。在实际应用中哈希表方法通常是首选因为它的时间复杂度更低更适合处理大规模数据。这种方法不仅适用于两数之和问题还可以应用于许多其他需要查找元素的问题例如三数之和、四数之和等。掌握哈希表的使用对于解决这类问题非常重要。