计算
安全
数据库
网络和加速
企业服务
# LeetCode中两数之和的案例分析
## 引言
在算法学习和面试准备中，LeetCode作为全球知名的编程题库，其题目往往成为衡量开发者算法能力的重要标准。其中，"两数之和"（Two Sum）作为题库的第一题，具有标志性意义。本文将通过详细分析该问题，探讨多种解题思路、时间复杂度的优化方法，以及在实际应用中的价值。
## 问题描述
**题目编号**：1
**题目名称**：两数之和
**难度**：简单
**描述**：
给定一个整数数组`nums`和一个整数目标值`target`，请你在该数组中找出**和为目标值**的那**两个**整数，并返回它们的数组下标。假设每种输入只会对应一个答案，且数组中同一个元素不能重复使用。
**示例**：
```python
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：nums[0] + nums[1] = 2 + 7 = 9
核心思想：
通过双重循环遍历所有可能的组合，检查是否存在满足条件的两个数。
代码实现：
def twoSum(nums, target):
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)
优缺点：
- 优点：实现简单，无需额外空间。
- 缺点：效率低，不适合大规模数据。
核心思想：
利用哈希表（字典）存储已遍历元素的值及其索引，通过检查target - current_value是否存在于哈希表中来快速定位解。
代码实现：
def twoSum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hashmap:
return [hashmap[complement], i]
hashmap[num] = i
return []
时间复杂度：O(n)
空间复杂度：O(n)
优缺点：
- 优点：时间效率显著提升。
- 缺点：需要额外空间存储哈希表。
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力枚举法 | O(n²) | O(1) | 小规模数据或教学示例 |
| 哈希表法 | O(n) | O(n) | 大规模数据或实际应用 |
优化思考：
- 如果输入数组已排序，可使用双指针法进一步优化空间复杂度至O(1)。
- 对于重复元素较多的场景，需考虑哈希冲突处理。
nums = [3,3], target = 6，需确保哈希表正确处理最后一次出现的索引。“两数之和”问题虽简单，但涵盖了算法设计的核心思想：暴力优化与空间换时间。通过本题，我们可以深入理解哈希表的高效查找机制，并为后续更复杂的算法问题打下基础。建议读者在掌握基础解法后，尝试自行实现排序+双指针的变种解法，以巩固学习成果。
附录：相关LeetCode题目推荐
- 15. 三数之和
- 167. 两数之和 II（有序数组）
- 170. 两数之和 III（数据结构设计）
“`
注：本文实际字数约1200字，可通过扩展代码注释、添加图表（如时间复杂度曲线）或详细案例分析进一步补充内容。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/3934278/blog/4679662
