1. 两数之和#

生活中的算法#

还记得上次去超市购物吗？你拿着一张100元钞票，挑选了一些商品，收银员告诉你总价是87元。这时候，收银员要找给你13元。但如果收银柜里只有零散的1元、5元、10元，收银员该如何快速地从这些零钱中找出两张，正好加起来等于13元呢？

这就是我们今天要讨论的”两数之和”问题在生活中的一个实例。

问题描述#

题目目标#

LeetCode第1题”两数之和”是这样描述的：给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

示例 1#

输入： nums = [2,7,11,15], target = 9 输出： [0,1] 说明： nums[0] + nums[1] == 9

最直观的解法：暴力穷举#

如果你是收银员，最直观的做法是什么？大概率是这样：拿起第一张钞票，然后挨个和其他钞票配对，看看加起来是不是13元。不行的话，再拿第二张钞票，继续和后面的钞票配对…

这就是我们的暴力解法，它朴素但有效。具体来说：

拿起第一个数字
依次与后面的每个数字相加，检查是否等于目标值
如果找到了，就返回这两个数字的位置
如果没找到，就拿起第二个数字，重复步骤2和3
以此类推，直到找到答案或检查完所有可能

让我们用一个具体的例子来模拟这个过程：

nums = [2, 7, 11, 15], target = 9
第一轮：拿起2
2 + 7 = 9，找到答案了！
返回[0, 1]
如果没这么幸运：
2 + 11 = 13，不是9，继续
2 + 15 = 17，不是9，继续
拿起7...

plaintext

这种思路可以用Java代码这样实现：

public int[] twoSum(int[] nums, int target) {
    // 外层循环变量 i：表示当前选中的第一个数字的下标
    for (int i = 0; i < nums.length; i++) {
        // 内层循环变量 j：从 i 后面开始，避免和自己配对，也避免重复比较
        for (int j = i + 1; j < nums.length; j++) {
            // 检查 nums[i] 和 nums[j] 的和是否正好等于目标值 target
            if (nums[i] + nums[j] == target) {
                // 命中答案：按题意返回这两个数的下标
                return new int[]{i, j};
            }
        }
    }
    // 边界情况：如果遍历完所有组合仍未找到，返回空数组（通常题目会保证有解）
    return new int[]{};
}

java

优化解法：哈希表#

让我们回到超市的场景。假设收银员手里拿着一张5元，要找给顾客13元。这时候收银员在想：我现在需要找一张8元的（13 - 5 = 8）。如果能立即知道柜台里有没有8元，问题就解决了。

这就是哈希表解法的核心思想：我们可以使用一个哈希表来记录每个数字出现的位置，这样就能在O(1)时间内查找任何数字。

哈希表解法的原理#

创建一个哈希表，用于存储每个数字及其下标
遍历数组中的每个数字current
计算需要配对的数字complement = target - current
在哈希表中查找complement
- 如果找到了，说明我们找到了答案
- 如果没找到，把当前数字和它的下标放入哈希表，继续遍历

算法步骤（伪代码）#

创建空的哈希表map
对于数组中的每个数字nums[i]：
- 计算complement = target - nums[i]
- 如果map中包含complement，返回[map.get(complement), i]
- 否则，将nums[i]和i放入map中
如果遍历完还没找到，返回空数组

示例运行#

让我们用示例数据模拟一下：

nums = [2, 7, 11, 15], target = 9

第一步：i = 0
- current = 2
- complement = 9 - 2 = 7
- map为空，找不到7
- 将2和它的下标0放入map：{2:0}

第二步：i = 1
- current = 7
- complement = 9 - 7 = 2
- 在map中找到了2！
- 返回[map.get(2), 1]，也就是[0, 1]

plaintext

Java代码实现#

public int[] twoSum(int[] nums, int target) {
    // map 的含义：key=数组中的某个数字，value=该数字对应的下标
    // 作用：支持 O(1) 平均时间复杂度的查找，快速判断“配对数”是否出现过
    Map<Integer, Integer> map = new HashMap<>();

    // 单次遍历数组：边查找配对值，边把当前值存入哈希表
    for (int i = 0; i < nums.length; i++) {
        // complement 表示“当前数字 nums[i] 还差多少才能凑成 target”
        int complement = target - nums[i];

        // 先查 map：如果 complement 已出现，说明已经找到一对答案
        if (map.containsKey(complement)) {
            // map.get(complement) 是配对数字的下标，i 是当前数字的下标
            return new int[]{map.get(complement), i};
        }

        // 若未找到配对值，则把当前数字及其下标记录到 map 中，供后续元素匹配
        // 注意顺序：必须先查再放，避免同一个元素被重复使用
        map.put(nums[i], i);
    }

    // 边界情况：若遍历结束仍无解，返回空数组（通常题目保证有解）
    return new int[]{};
}

java

暴力解法vs哈希表解法#

让我们比较一下这两种解法：暴力解法用两层循环检查所有可能的组合，时间复杂度是O(n²)，但空间复杂度只有O(1)。它的优点是直观、易于理解，适合处理小规模数据。

哈希表解法只需要遍历一次数组，时间复杂度是O(n)，但需要额外的哈希表存储数据，空间复杂度是O(n)。它用空间换时间，特别适合处理大规模数据。

题目模式总结#

这道题虽然简单，但它体现了一个重要的算法模式：查找配对元素。

这种模式在算法题中经常出现，比如：

判断数组中是否存在两个数的差等于某个值
在排序数组中找出两个数，它们的平方和等于某个值
在字符串中找出两个字符，它们的ASCII码之和等于某个值

解决这类问题的通用思路是：

先思考暴力解法：两层循环遍历所有可能的组合
考虑优化：能否将”查找配对元素”的过程优化到O(1)时间复杂度
思考数据结构：通常哈希表是优化这类问题的利器

小结#

通过这道题，我们不仅学会了如何解决”两数之和”，更重要的是理解了一个常见的算法模式。下次遇到类似的”找配对元素”问题，我们就知道该如何思考了。

学习算法最重要的不是背解法，而是理解思维方式。希望这篇文章对你有帮助！