LeetCode如何判断两数之和的结果是否等于给定的目标结果

# LeetCode如何判断两数之和的结果是否等于给定的目标结果

## 引言

在算法学习和编程面试中，"两数之和"（Two Sum）是一个经典且基础的问题。它不仅是LeetCode上的第一道题目，也是许多开发者接触算法问题的起点。本文将深入探讨如何判断数组中是否存在两个数，它们的和等于给定的目标值，并分析不同解法的优劣。

---

## 问题描述

**题目**：  
给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出**和为目标值**的那**两个**整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，且同一个元素不能重复使用。

**示例**：
```python
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：nums[0] + nums[1] = 2 + 7 = 9

---

解法一：暴力枚举法

思路分析

最直观的方法是遍历数组中的每一个元素 x，并查找是否存在另一个元素 y 满足 x + y = target。

代码实现

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)，仅使用常数级别的额外空间。

适用场景

适用于小规模数据（如 n < 1000），但面对大规模数据时效率极低。

---

解法二：哈希表（字典）优化

思路分析

通过空间换时间，利用哈希表（Python中为字典）存储已遍历的元素及其索引。对于当前元素 x，检查 target - x 是否在哈希表中。

代码实现

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

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组，哈希表查询操作平均为 O(1)。
• 空间复杂度：O(n)，需要存储最多 n 个元素的哈希表。

优势

• 效率显著提升，适合处理大规模数据。
• 代码简洁，逻辑清晰。

---

解法三：排序 + 双指针

思路分析

1. 先对数组排序。
2. 使用双指针从两端向中间移动，根据和与 target 的比较调整指针位置。

代码实现

def twoSum(nums, target):
    sorted_nums = sorted(zip(nums, range(len(nums))), key=lambda x: x[0])
    left, right = 0, len(sorted_nums) - 1
    while left < right:
        current_sum = sorted_nums[left][0] + sorted_nums[right][0]
        if current_sum == target:
            return [sorted_nums[left][1], sorted_nums[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

复杂度分析

• 时间复杂度：O(n log n)，排序占主导。
• 空间复杂度：O(n)，需要额外空间存储带索引的元组。

注意事项

• 返回的是原始索引，排序后需保留索引信息。
• 不适用于需要频繁查询的场景（因每次需重新排序）。

---

边界条件与异常处理

常见边界情况

1. 无解情况：如 nums = [1,2,3], target = 7，应返回空列表。
2. 重复元素：如 nums = [3,3], target = 6，需正确处理。
3. 负数与零：如 nums = [-1,0,1], target = 0。

代码健壮性建议

• 添加输入合法性检查（如非空数组）。
• 处理多解时明确返回规则（如题目保证唯一解可忽略）。

---

不同语言的实现差异

Python示例

利用字典的简洁性：

hash_map = {}
for i, num in enumerate(nums):
    ...

Java示例

使用 HashMap：

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    ...
}

C++示例

使用 unordered_map：

unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
    ...
}

---

实际应用场景

1. 金融系统：查找股票价格组合达到目标收益。
2. 游戏开发：匹配物品属性组合触发特效。
3. 数据分析：快速筛选满足条件的数值对。

---

总结

解法	时间复杂度	空间复杂度	适用场景
暴力枚举	O(n²)	O(1)	小规模数据
哈希表	O(n)	O(n)	大规模数据
排序+双指针	O(n log n)	O(n)	需有序数据时

推荐选择：哈希表解法在大多数情况下最优，兼顾效率与代码可读性。

---

扩展思考

1. 三数之和：如何扩展为求解三个数的组合？（LeetCode 15题）
2. 重复答案：若允许重复答案，如何修改算法？
3. 流式数据：数据以流形式输入时如何优化？

---

参考资料

1. LeetCode Two Sum Problem
2. 《算法导论》—— Thomas H. Cormen
3. 《编程珠玑》—— Jon Bentley

”`