手帐 Blog

主题

03 · 先暴力再优化 · 两数之和 ​

目标：对 LeetCode 1 写出暴力解和 Map 哈希解，并养成「先暴力再优化」的习惯。

为什么面试会考 ​

LeetCode 1. 两数之和 是前端算法面试的「/hello world」。考你能不能：

  1. 先把题意翻译成代码（暴力）。
  2. 发现慢在哪，用空间换时间（哈希）。
  3. 口述清楚复杂度变化。

零基础概念：先暴力再优化 ​

text
第一步：暴力 — 能跑、能提交、建立信心
第二步：找瓶颈 — 哪一步重复做了？
第三步：加结构 — Map / 双指针 / 排序 等消掉重复

面试时先讲暴力，再讲优化，比一上来憋「最优解」更稳。

零基础概念：哈希表在找配对题里的角色 ​

问：有没有两个数加起来等于 target？

暴力：两两试，慢。
优化：遍历 x 时，问「target - x 之前见过吗？」——用 Map 记「值 → 下标」。

JS 模板 / 套路：一遍遍历 + Map ​

javascript
// 找配对：need = target - current
// Map: 值 -> 下标
const map = new Map();
for (let i = 0; i < nums.length; i++) {
  const need = target - nums[i];
  if (map.has(need)) return [map.get(need), i];
  map.set(nums[i], i);
}

精讲 1：LeetCode 1. 两数之和 — 暴力 O(n²) ​

题意：数组 nums、整数 target，返回两个下标 i、j，使 nums[i] + nums[j] === target。保证恰有一组解。

javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSumBrute = function(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];
      }
    }
  }
  return [];
};
  • 时间 O(n²)，空间 O(1)。
  • 优点：最好想。缺点：n 大就超时。

精讲 2：LeetCode 1. 两数之和 — Map O(n) ​

javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const map = new Map(); // 值 -> 下标
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) {
      return [map.get(need), i];
    }
    map.set(nums[i], i);
  }
  return [];
};
  • 时间 O(n)，空间 O(n)。
  • 关键：先查再存。同一下标不能用自己配自己。

精讲 3：LeetCode 167. 两数之和 II — 有序数组双指针（引入） ​

题意：有序数组，找两个数之和为 target，返回 1-based 下标。与第 1 题不同：已排序，不能用 Map 乱序那套，常用左右指针。

javascript
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSumSorted = function(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) return [left + 1, right + 1];
    if (sum < target) left++;
    else right--;
  }
  return [];
};
  • 时间 O(n)，空间 O(1)。
  • 对比：无序 → Map；有序 → 双指针（第 05 篇会展开）。

练习清单 ​

题号一句话提示
LeetCode 1. 两数之和暴力 + Map 各写一遍
LeetCode 167. 两数之和 II有序数组，左右指针
LeetCode 15. 三数之和排序 + 固定一端 + 双指针（进阶）
LeetCode 170. 两数之和 III设计类：用 Set 判 need 是否存在

今日验收 checklist ​

  • [ ] 能闭卷写出 LeetCode 1 的 Map 解并提交通过
  • [ ] 能口述：暴力 O(n²) 慢在哪，Map 如何省时间
  • [ ] 说清「无序用 Map，有序用双指针」
  • [ ] 尝试写出 167 的双指针解

若你以前见过 ​

C++ unordered_map、Python dict 同一套路。JS 注意：map.get(need) 可能得到 0，是合法下标，不能用 if (!map.get(need)) 判断存在，要用 map.has(need)。