前置知识点解析

时间复杂度

时间复杂度用大 O 符号（O）来表示，它描述了算法运行时间与输入数据大小之间的关系。简单来说，它告诉我们当输入数据越来越大时，算法的运行时间会如何变化。 让我们通过具体例子来理解常见的时间复杂度：

1. O(1) - 常数时间

const getFirstElement = (arr) => {
  return arr[0]; // 只执行一次，不管数组多大
};

• 含义：无论输入数据多大，执行时间都是固定的
• 例子：数组取第一个元素、Map 的查找操作
• 特点：最快的时间复杂度

2. O(n) - 线性时间

const findNumber = (arr, target) => {
  for (let i = 0; i < arr.length; i++) {
    // 遍历一次数组
    if (arr[i] === target) return i;
  }
};

• 含义：执行时间与输入数据大小成正比
• 例子：遍历一次数组
• 特点：随着数据量增加，执行时间线性增加

3. O(n²) - 平方时间

// 就像我们的暴力解法
const twoSumBruteForce = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    // 第一层循环
    for (let j = i + 1; j < nums.length; j++) {
      // 第二层循环
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

• 含义：执行时间与输入数据大小的平方成正比
• 例子：嵌套循环
• 特点：数据量增加时，执行时间增加很快

实际比较

假设我们有一个长度为 n 的数组，比较不同时间复杂度的实际执行次数：

当 n = 100 时：
O(1)   → 1次操作
O(n)   → 100次操作
O(n²)  → 10,000次操作

当 n = 1000 时：
O(1)   → 1次操作
O(n)   → 1,000次操作
O(n²)  → 1,000,000次操作

回到两数之和题目

1. 暴力解法 O(n²)：

// 需要两层循环，对于长度为n的数组
// 外层循环运行n次
// 内层循环每次最多运行n次
// 总操作次数约为 n × n = n²

2. 哈希表解法 O(n)：

// 只需要一次循环
// Map的查找（has）和存储（set）操作都是O(1)
// 总操作次数与数组长度n成正比

为什么哈希表解法更好？

以数组长度 100 为例：

• 暴力解法：最多需要 100 × 100 = 10,000 次操作
• 哈希表解法：只需要 100 次循环 + 100 次 Map 操作 = 200 次操作

这就是为什么在处理大规模数据时，我们要尽量避免 O(n²)的解法，优先使用 O(n)或 O(1)的解法。

需要我详细解释任何部分吗？或者我们可以通过更多具体的例子来加深理解。