Vue.js

Appearance

On this page

实战：两数之和 ​

从这一章开始，我们进入 LeetCode 实战。

「两数之和」是 LeetCode 的第 1 题，也是几乎所有人刷 LeetCode 的起点。这道题虽然简单，但包含了一个重要的优化思想：用空间换时间。

题目描述 ​

LeetCode 1. 两数之和

给定一个整数数组 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]

提示：

  • 2 ≤ nums.length ≤ 10⁴
  • -10⁹ ≤ nums[i] ≤ 10⁹
  • 只会存在一个有效答案

题目分析 ​

核心问题：找两个数 nums[i] + nums[j] = target。

关键约束：

  1. 两个数的索引不能相同（i ≠ j）
  2. 题目保证只有一个有效答案
  3. 数组长度最大 10⁴

思考方向：

  • 最直接的方法：枚举所有两数组合，检查它们的和
  • 能否优化？对于每个 nums[i]，我们需要找 target - nums[i]
  • 这是一个查找问题——考虑使用哈希表

解法一：暴力枚举 ​

最直接的思路：两层循环，枚举所有可能的两数组合。

javascript
function twoSum(nums, target) {
    const n = nums.length;
    
    // 外层循环：选第一个数
    for (let i = 0; i < n; i++) {
        // 内层循环：选第二个数
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    
    return [];  // 题目保证有解，不会执行到这里
}

为什么内层从 i + 1 开始？

因为我们不想重复检查。如果内层从 0 开始：

  • (i=0, j=1) 和 (i=1, j=0) 实际上是同一对数
  • 而且 i === j 时会用同一个元素两次，违反题目要求

从 i + 1 开始，既避免重复，又保证 i ≠ j。

复杂度分析：

  • 时间复杂度：O(n²)——两层循环
  • 空间复杂度：O(1)——只用了几个变量

评价：这个解法可以通过 LeetCode，但不是最优。n = 10⁴ 时，10⁸ 次操作，有点慢。

解法二：哈希表优化 ​

暴力法的瓶颈在于：对于每个 nums[i]，需要 O(n) 时间去找 target - nums[i]。

能否把查找时间降到 O(1)？

可以。用哈希表。

核心思想：一边遍历，一边把已经见过的数存入哈希表。对于当前的 nums[i]，检查 target - nums[i] 是否已经在哈希表中。

javascript
function twoSum(nums, target) {
    // 哈希表：值 -> 索引
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        // 计算需要的配对数
        const complement = target - nums[i];
        
        // 检查配对数是否已存在
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        
        // 将当前数存入哈希表
        map.set(nums[i], i);
    }
    
    return [];
}

执行过程 ​

以 nums = [2, 7, 11, 15], target = 9 为例：

i=0: nums[0] = 2
     需要找: 9 - 2 = 7
     map: {} → 没有 7
     存入: {2: 0}

i=1: nums[1] = 7
     需要找: 9 - 7 = 2
     map: {2: 0} → 有 2！索引是 0
     返回 [0, 1] ✓

只遍历了 2 个元素就找到了答案。

为什么不会找到自己？ ​

注意代码的顺序：先查找，后存入。

当我们检查 nums[i] 时，nums[i] 还没有被存入哈希表，所以不可能找到自己。

这一点对于示例 3 很重要：nums = [3, 3], target = 6。

i=0: nums[0] = 3
     需要找: 6 - 3 = 3
     map: {} → 没有 3（自己还没存入）
     存入: {3: 0}

i=1: nums[1] = 3
     需要找: 6 - 3 = 3
     map: {3: 0} → 有 3！索引是 0
     返回 [0, 1] ✓

如果我们先存入后查找，i=0 时就会找到自己，返回 [0, 0]，这是错的。

复杂度分析：

  • 时间复杂度：O(n)——只遍历一次数组
  • 空间复杂度：O(n)——哈希表最多存储 n 个元素

两种解法对比 ​

解法时间复杂度空间复杂度特点
暴力枚举O(n²)O(1)简单直观，不需要额外空间
哈希表O(n)O(n)时间最优，需要额外空间

这就是经典的时间-空间权衡。用 O(n) 的空间换来了 O(n) 的时间（相比 O(n²)）。

在大多数场景下，我们会选择哈希表解法。因为内存通常不是瓶颈，而时间对用户体验影响很大。

边界情况 ​

javascript
// 基本测试
console.log(twoSum([2, 7, 11, 15], 9));  // [0, 1]
console.log(twoSum([3, 2, 4], 6));       // [1, 2]

// 相同元素
console.log(twoSum([3, 3], 6));          // [0, 1]

// 包含零
console.log(twoSum([0, 0], 0));          // [0, 1]

// 负数
console.log(twoSum([-1, -2, -3, -4], -6)); // [1, 3]

常见错误 ​

  1. 返回值搞错：题目要求返回索引，不是元素值
  2. 同一元素用两次：如 [3, 2, 4], target=6，不能返回 [0, 0]
  3. 先存后查：可能导致找到自己

相关题目 ​

如果你掌握了两数之和，可以尝试这些进阶题目：

  • 167. 两数之和 II：数组有序，能否用 O(1) 空间？（提示：双指针）
  • 15. 三数之和：找三个数，它们的和为 0
  • 18. 四数之和：进一步扩展

本章小结 ​

两数之和虽然是"简单题"，但它揭示了一个重要的优化模式：

  1. 暴力法：O(n²) 时间，O(1) 空间
  2. 哈希表：O(n) 时间，O(n) 空间
  3. 核心思想：把"查找配对数"的时间从 O(n) 降到 O(1)

这个"空间换时间"的思想会在后续很多题目中反复出现。记住它。

下一章，我们来看另一道经典题目：「删除排序数组中的重复项」。

在 GitHub 上编辑此页