LeetCode 1. 两数之和 - 从暴力解法到最优解法的完整分析

LeetCode 1. 两数之和 - 从暴力解法到最优解法的完整分析

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

示例：

输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

题目分析

这是一道经典的数组查找问题，核心思想是：

1. 在数组中找到两个不同的元素
2. 这两个元素的和等于目标值
3. 返回这两个元素的下标

解法一：暴力解法（我最开始的解法）

刚开始没有好的思路，所以我只想到了用枚举法，然后让后一个元素从前一个元素+1开始，这样可以节省一半的时间

代码实现

def twoSum_brute_force(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return []

算法分析

• 时间复杂度：O(n²) - 双重循环
• 空间复杂度：O(1) - 只使用常数额外空间
• 优点： 思路简单，容易理解
• 缺点： 时间复杂度高，在大数据量时性能差

缺陷分析

1. 时间复杂度问题：O(n²) 的时间复杂度对于大数据量（题目提示 n ≤ 10⁴）来说效率较低
2. 缺少边界处理：没有处理找不到解的情况（虽然题目保证有解）
3. 代码可读性：变量命名可以更清晰（e 改为 j 更直观）

解法二：哈希表解法（最优解法）

核心思想

使用哈希表存储已遍历的元素，对于当前元素 num，检查 target - num 是否在哈希表中。

代码实现

def twoSum_hash_map(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 []

算法分析

• 时间复杂度：O(n) - 只需要一次遍历
• 空间复杂度：O(n) - 哈希表存储最多 n 个元素
• 优点： 时间复杂度最优，实际运行效率高
• 缺点： 需要额外的哈希表空间

算法流程

1. 遍历数组，对于每个元素 nums[i]
2. 计算补数 complement = target - nums[i]
3. 检查补数是否在哈希表中
4. 如果在，返回 [hash_map[complement], i]
5. 如果不在，将当前元素及其索引加入哈希表

解法三：双指针解法

核心思想

先对数组排序，然后使用双指针从两端向中间移动。

代码实现

def twoSum_two_pointers(self, nums: List[int], target: int) -> List[int]: # 创建索引数组，保持原始索引 indexed_nums = [(nums[i], i) for i in range(len(nums))] indexed_nums.sort(key=lambda x: x[0]) left, right = 0, len(nums) - 1 while left < right: current_sum = indexed_nums[left][0] + indexed_nums[right][0] if current_sum == target: return [indexed_nums[left][1], indexed_nums[right][1]] elif current_sum < target: left += 1 else: right -= 1 return []

算法分析

• 时间复杂度：O(nlogn) - 排序 + 双指针遍历
• 空间复杂度：O(n) - 需要额外的索引数组
• 优点： 思路清晰，适合理解双指针思想
• 缺点： 时间复杂度不如哈希表解法，且需要额外处理索引

性能对比

解法 时间复杂度 空间复杂度 适用场景 暴力解法 O(n²) O(1) 小数据量，教学演示 哈希表解法 O(n) O(n) 最优解法，实际应用 双指针解法 O(nlogn) O(n) 需要保持数组有序的场景

完整测试代码

from typing import Listimport timeclass Solution: def twoSum_brute_force(self, nums: List[int], target: int) -> List[int]: \"\"\"暴力解法\"\"\" for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target:  return [i, j] return [] def twoSum_hash_map(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 [] def twoSum_two_pointers(self, nums: List[int], target: int) -> List[int]: \"\"\"双指针解法\"\"\" indexed_nums = [(nums[i], i) for i in range(len(nums))] indexed_nums.sort(key=lambda x: x[0]) left, right = 0, len(nums) - 1 while left < right: current_sum = indexed_nums[left][0] + indexed_nums[right][0] if current_sum == target: return [indexed_nums[left][1], indexed_nums[right][1]] elif current_sum < target: left += 1 else: right -= 1 return []# 性能测试def performance_test(): import random # 生成测试数据 n = 10000 nums = [random.randint(-1000, 1000) for _ in range(n)] target = random.randint(-1000, 1000) solution = Solution() # 测试哈希表解法 start_time = time.time() result1 = solution.twoSum_hash_map(nums, target) hash_time = time.time() - start_time # 测试双指针解法 start_time = time.time() result2 = solution.twoSum_two_pointers(nums, target) pointer_time = time.time() - start_time print(f\"数据量: {n}\") print(f\"哈希表解法耗时: {hash_time:.6f}秒\") print(f\"双指针解法耗时: {pointer_time:.6f}秒\") print(f\"结果一致: {sorted(result1) == sorted(result2)}\")if __name__ == \"__main__\": performance_test()

总结

1. 原始解法虽然能正确解决问题，但在时间复杂度上存在优化空间
2. 哈希表解法是最优解法，时间复杂度 O(n)，适合实际应用
3. 双指针解法虽然时间复杂度较高，但有助于理解双指针思想
4. 在实际面试中，建议先说出暴力解法，然后优化到哈希表解法

进阶思考

• 如果数组已经排序，双指针解法的时间复杂度会降到 O(n)
• 如果要求返回所有可能的解，需要修改哈希表解法
• 如果数组中有重复元素，需要特别注意处理逻辑

这道题是算法学习的经典入门题，掌握多种解法有助于提升算法思维！