哈希

作者:青见春山

发表于:2026-09-08

字数统计:21316 字

预计阅读72分钟

基础概念：

数组是存放在连续内存空间上的相同类型数据的集合。

因为数组在内存空间的地址是连续的，所以我们在删除或者增加元素的时候，就难免要移动其他元素的地址。

1.两数之和easy

暴力解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
   for (let i = 0; ; i++) { // 枚举 i
        for (let j = i + 1; j < nums.length; j++) { // 枚举 i 右边的 j
            if (nums[i] + nums[j] === target) { // 满足要求
                return [i, j]; // 返回两个数的下标
            }
        }
    }
    // 题目保证有解，循环中一定会 return
    // 所以这里无需 return，毕竟代码不会执行到这里
};

时间复杂度：O(n^2)，其中 n 为 nums 的长度。
空间复杂度：O(1)。仅用到若干额外变量。

哈希表写法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const idx = new Map(); // 创建一个空哈希表
    //map是es6提供的哈希映射（键值对）
    for (let j = 0; ; j++) { // 枚举 j
        const x = nums[j];
        // 在左边找 nums[i]，满足 nums[i]+x=target
        if (idx.has(target - x)) { // 找到了
            return [idx.get(target - x), j]; // 返回两个数的下标
        }
        idx.set(x, j); // 保存 nums[j] 和 j
    }
};

时间复杂度：O(n)，其中 n 为 nums 的长度。
空间复杂度：O(n)。哈希表需要 O(n) 的空间。
相比暴力做法，哈希表多消耗了内存空间，但减少了运行时间，这就是「空间换时间」。

关键知识点补充

1. 为什么用 Map 而不是普通对象 {}？
   • Map 的键可以是任意类型（对象、NaN 都行），而对象的键会被转成字符串。
   • Map 有明确的 size，迭代次序更可控，性能也更适合做哈希表。
   • 这题用对象也能做，但 Map 更语义化、少坑。
2. const 与“可变”
   • const idx = new Map()：表示 idx 这个变量不能被重新赋值，但 idx 指向的 Map 里的内容是可以 .set() 增加的。
3. 为什么检查 has() 再 get()？
   • 如果你先 get() 再判断真值：当索引是 0 时，0 在 JS 里是“假”，容易误判。
   • has() 明确告诉你键是否存在，避免 “0 被当成 false” 这种坑。
4. 重复元素会不会搞乱？
   • 不会。因为我们总是先查补数再把当前值写进表，保证不会用到同一个元素两次。
   • 例如 nums = [3,3]，target=6：
     • j=0：idx 还没 3，先存 {3:0}；
     • j=1：发现 idx.has(3)，返回 [0,1]。
5. 无限循环的隐患
   • 你当前写法 for (let j = 0; ; j++) 在没有答案时会“跑飞”。
   • 实战要么写 j < nums.length，要么最后抛错/返回空数组。

49.字母异位词分组

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const m = new Map();
  //创建一个映射表（哈希表），键是“排序后的字符串”，值是“一个数组，装原始字符串”。
  for (const s of strs) {
    // for...of 遍历“可迭代对象”，这里就是数组。
    // 把 s 排序，作为哈希表的 key
    const sortedS = s.split("").sort().join("");
    //s.split('')把字符串 拆成字符数组。字符串是不可变的（immutable），所以要先变成数组才能排序。
    //.sort()原地给数组排序（会修改这个数组本身）。**默认是按 UTF-16 码点“字典序”**排序。对英文字母效果刚好就是我们想要的“a..z”顺序（区分大小写）。
    //.join('')把排好序的字符数组 再拼回字符串。这里没有传比较函数，因为按字符排序默认就够用。
    if (!m.has(sortedS)) {
      m.set(sortedS, []);
    }
    // 排序后相同的字符串分到同一组
    m.get(sortedS).push(s);
  }
  // 哈希表的 value 保存分组后的结果
  return Array.from(m.values());
};

小扩展

• Map.values() 返回的是迭代器，Array.from(...) 或 [...m.values()] 都能把它转成数组。
• 稳定性：我们只需要把“同类”放在一起，组内顺序无要求；如果想让组内也按字典序，可以在最终 map([...]) 中再 sort() 一次每组。
• 大小写/非英文：若输入大小写混合，"Eat" 与 "eat" 不会分到一起（因为 "Eat" 排序成 "Eat"，"eat" 排序成 "aet"）。需要忽略大小写就先 .toLowerCase()。

128.最长连续序列

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const st = new Set(nums); // 把 nums 转成哈希集合
//自动 去重（重复元素只保留一份）。
//提供 O(1) 平均时间 的查找：st.has(value) 很快。
    let ans = 0;
    for (const x of st) { // 遍历哈希集合
        if (st.has(x - 1)) { // 如果 x 不是序列的起点，直接跳过
            continue;
        }
        //如果 x - 1 也在集合里，说明 x 前面还有更小的连续数，那 x 肯定不是起点，直接跳过，避免重复计算。
//意义：这一步保证了 每条连续链只从最小的那个数开始数一次，从而把整体复杂度控制在 O(n)。

        // x 是序列的起点
        let y = x + 1;
        //从起点 x 的下一个数开始，准备向右扩展序列。
        while (st.has(y)) { // 不断查找下一个数是否在哈希集合中
            y++;
        }
        // 循环结束后，y-1 是最后一个在哈希集合中的数
        ans = Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
     // 更新最长长度。
//因为从 x 数到 y-1，包含的元素个数是 (y-1) - x + 1 = y - x。
//举例：x=1, y=5 ⇒ 序列是 1,2,3,4，长度 5-1=4。
    }
    return ans;
};
复杂度分析
时间复杂度：O(n)，其中 n 是 nums 的长度。在二重循环中，每个元素至多遍历两次：在外层循环中遍历一次，在内层循环中遍历一次。所以二重循环的时间复杂度是 O(n) 的。比如 nums=[1,2,3,4]，其中 2,3,4 不会进入内层循环，只有 1 会进入内层循环。
空间复杂度：O(m)。其中 m 是 nums 中的不同元素个数

走一遍例子（跳过非起点”的妙处）

输入：[100, 4, 200, 1, 3, 2, 2]

1. st = {100, 4, 200, 1, 3, 2}（重复的 2 被去掉）
2. 遍历 st（顺序无所谓，这里按展示顺序说明）：
   • x = 100：st.has(99) 为假 ⇒ 起点
     • 数：101 不在 ⇒ 长度 1，ans=1
   • x = 4：st.has(3) 为真 ⇒ 不是起点，跳过
   • x = 200：st.has(199) 为假 ⇒ 起点
     • 数：201 不在 ⇒ 长度 1，ans=1
   • x = 1：st.has(0) 为假 ⇒ 起点
     • 数：2 在 → 3 在 → 4 在 → 5 不在 ⇒ 长度 4，ans=4
   • x = 3：st.has(2) 为真 ⇒ 跳过
   • x = 2：st.has(1) 为真 ⇒ 跳过
3. 返回 ans = 4（最长是 1,2,3,4）。

你会发现：同一条连续链只有最小的那个数（1）会触发 while 扩展，链中其它数（2、3、4）都被“不是起点”的判断跳过了，所以不会重复数，复杂度才是 O(n)。

数组

53.最大子数组和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let ans = nums[0];
  //用 ans 保存当前遇到的最大子数组和
  let sum = 0;
  //sum 保存「以当前元素结尾的、可扩展的子数组的最大和（当前子数组和）」
  for (const num of nums) {
    if (sum > 0) {
      sum += num;
    } else {
      sum = num;
    }
    //核心：如果之前的 sum 是正数，说明把它和当前 num 连在一起能让和变大（有扩展的价值），就 sum += num；否则以前的和非正数时，把之前的部分丢弃，从当前元素重新开始 sum = num（因为之前的非正和加到当前会使当前和更差）。
    ans = Math.max(ans, sum);
    //每步更新全局最大值 ans。
  }
  return ans;
  //遍历完返回最大子数组和。
};

如果当前的累积和 sum ≤ 0，把它加到后面的任何子数组上都不会让和变大（甚至会变小或不变），因此最好从下一个元素重新开始。反之 sum > 0 时，继续扩展是有利的。这个贪心决策在每一步只需局部判断，能在线性时间找到全局最优解。

时间复杂度：O(n)，一次遍历。

空间复杂度：O(1)，只用常数额外空间。

边界与注意事项

• 如果 nums 为空（[]），当前代码会访问 nums[0] 出错。可以在开头加个判断：if (nums.length === 0) return 0; 或抛出异常，按需求处理。
• JS 数值是 IEEE754 双精度（Number），若输入和可能超过 Number.MAX_SAFE_INTEGER（约 2^53），要注意精度问题；可考虑用 BigInt（但需改写逻辑）。
• if (sum > 0) 中用 > 还是 >=，对结果和最优值没有影响（数学上等价），但对起始索引追踪的实现会影响哪一端被视为“重新开始”的位置（通常两者都可）。

56.合并区间

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  intervals.sort((p, q) => p[0] - q[0]); // 按照左端点从小到大排序
  const ans = [];
  //结果数组ans
  for (const p of intervals) {
    const m = ans.length;
    //在 if (m && ...) 里，JavaScript 会把数字 0 当作 假值 (false)，非零数字当作 真值 (true)。
    if (m && p[0] <= ans[m - 1][1]) {
      // 若当前区间左端点 <= ans 最后区间的右端点，则可合并
      ans[m - 1][1] = Math.max(ans[m - 1][1], p[1]); // 更新右端点为两者右端点的较大者
    } else {
      // 不相交，无法合并
      ans.push(p);
      // 把当前区间作为新的合并区间加入结果
    }
  }
  return ans;
};

具体算法如下：

把 intervals[0] 加入答案。注意，答案的最后一个区间表示当前正在合并的区间。 遍历到 intervals[1]=[2,6]，由于左端点 2 不超过当前合并区间的右端点 3，可以合并。由于右端点 6>3，那么更新当前合并区间的右端点为 6。注意，由于我们已经按照左端点排序，所以 intervals[1] 的左端点 2 必然大于等于合并区间的左端点，所以无需更新当前合并区间的左端点。 遍历到 intervals[2]=[8,10]，由于左端点 8 大于当前合并区间的右端点 6，无法合并（两个区间不相交）。再次利用区间按照左端点排序的性质，更后面的区间的左端点也大于 6，无法与当前合并区间相交，所以当前合并区间 [1,6] 就固定下来了，把新的合并区间 [8,10] 加入答案。 遍历到 intervals[3]=[15,18]，由于左端点 15 大于当前合并区间的右端点 10，无法合并（两个区间不相交），我们找到了一个新的合并区间 [15,18] 加入答案。 上述算法同时说明，按照左端点排序后，合并的区间一定是 intervals 中的连续子数组。

• 时间复杂度：O(nlogn)，其中 n 是 intervals 的长度。瓶颈在排序上。
• 空间复杂度：O(1)。排序的栈开销和返回值不计入。

数组轮转

要求原地（in-place）修改，不用额外的线性空间。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  function reverse(i, j) {
    while (i < j) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
      j--;
    }
  }
  //双指针交换，直到i>=j

  const n = nums.length;
  k %= n; // 轮转 k 次等于轮转 k % n 次
  //把k规范到0。。n-1之间
  reverse(0, n - 1);
  reverse(0, k - 1);
  reverse(k, n - 1);
};

这里假设 0≤k<n，对于 k≥n 的情况，可以转换成 0≤k<n 的情况（证明见后文）。

设 nums=A+B，其中 A 是 nums 的前 n−k 个数，B 是后 k 个数。在上例中，A=[1,2,3,4]，B=[5,6,7]。

题目要求把 A+B 变成 B+A，这可以用三次反转实现：

把 nums 反转，我们得到了 rev(B)+rev(A)，其中 rev(A) 表示数组 A 反转后的结果。在上例中，rev(B)+rev(A)=[7,6,5]+[4,3,2,1]。 单独反转 rev(B)，因为一个数组反转两次是不变的，所以 rev(rev(B))=B，我们得到了 B。 单独反转 rev(A)，得到 A。 现在数组变成 B+A。在上例中，B+A=[5,6,7]+[1,2,3,4]，这正是我们想要的结果。

把旋转分成三步：

1. 把整个数组反转：reverse(0, n-1)。 这一步会把原数组的末 k 个元素移动到数组开头位置，但顺序是反的。
2. 把前 k 个元素反转：reverse(0, k-1)。 把第 1 步放到开头的那段恢复成正确的顺序。
3. 把剩下的 n-k 个元素反转：reverse(k, n-1)。 把第 1 步移动到后半部分的元素恢复成正确顺序。

这三次反转把数组“整体倒过来”再把两段分别倒回来，从而达到右移 k 的效果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 的长度。
• 空间复杂度：O(1)。

双指针交换

把数组 nums 的下标区间 [i, j] 内的元素就地反转。

function reverse(i, j) {
    while (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]]; // 用解构交换两个元素
        i++;
        j--;
    }
}

nums = [1,2,3,4,5];
reverse(1,3);
// 把下标 1 到 3（即 [2,3,4]）反转成 [4,3,2]
nums 变成 [1,4,3,2,5]

运行逻辑（逐行解析）

1. while (i < j)

   • 用两个指针：i 从左边开始，j 从右边开始。
   • 当 i >= j 时，说明左右已经交叉或相遇，反转完成。

2. [nums[i], nums[j]] = [nums[j], nums[i]];

   • 这是 ES6 解构赋值的用法，用来交换两个变量的值。

   • 等价于传统写法：

     let temp = nums[i];
     nums[i] = nums[j];
     nums[j] = temp;

3. i++; j--;

   • 交换完成后，把左指针右移一格，右指针左移一格，继续处理中间的元素。
   • 最终会把整个区间翻转。

let a = 1,
  b = 2;
[a, b] = [b, a];
console.log(a, b); // 2 1

其实就是先有右边的临时数组值，然后赋值给左边

238.除自身以外数组的乘积

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const n = nums.length;
  // 1. 构建前缀乘积数组 pre
  const pre = Array(n);
  pre[0] = 1;
  for (let i = 1; i < n; i++) {
    pre[i] = pre[i - 1] * nums[i - 1];
  }
  // 2. 构建后缀乘积数组 suf
  const suf = Array(n);
  suf[n - 1] = 1;
  for (let i = n - 2; i >= 0; i--) {
    suf[i] = suf[i + 1] * nums[i + 1];
  }
  // 3. 组合前缀和后缀得到最终答案
  const ans = Array(n);
  for (let i = 0; i < n; i++) {
    ans[i] = pre[i] * suf[i];
  }
  return ans;
};

前缀乘积数组 pre

pre[0] = 1;
for (let i = 1; i < n; i++) {
    pre[i] = pre[i - 1] * nums[i - 1];
}

目的：pre[i] 表示 索引 i 左边所有元素的乘积。

举例： 假设 nums = [1, 2, 3, 4]

• 初始化：pre[0] = 1
• i = 1：pre[1] = pre[0] * nums[0] = 1 * 1 = 1
• i = 2：pre[2] = pre[1] * nums[1] = 1 * 2 = 2
• i = 3：pre[3] = pre[2] * nums[2] = 2 * 3 = 6

最终 pre = [1, 1, 2, 6]

后缀乘积数组 suf

suf[n - 1] = 1;
for (let i = n - 2; i >= 0; i--) {
    suf[i] = suf[i + 1] * nums[i + 1];
}

目的：suf[i] 表示 索引 i 右边所有元素的乘积。

举例：nums = [1, 2, 3, 4]

• 初始化：suf[3] = 1
• i = 2：suf[2] = suf[3] * nums[3] = 1 * 4 = 4
• i = 1：suf[1] = suf[2] * nums[2] = 4 * 3 = 12
• i = 0：suf[0] = suf[1] * nums[1] = 12 * 2 = 24

最终 suf = [24, 12, 4, 1]

组合前缀和后缀得到答案

const ans = Array(n);
for (let i = 0; i < n; i++) {
    ans[i] = pre[i] * suf[i];
}

逻辑：

• ans[i] = pre[i] * suf[i]
• 前缀乘积 × 后缀乘积 = 除自身以外的乘积

举例：pre = [1, 1, 2, 6], suf = [24, 12, 4, 1]

• i = 0: 1 * 24 = 24
• i = 1: 1 * 12 = 12
• i = 2: 2 * 4 = 8
• i = 3: 6 * 1 = 6

最终 ans = [24, 12, 8, 6] ✅

核心思路

1. 前缀乘积 → 保存每个元素左边所有元素的乘积
2. 后缀乘积 → 保存每个元素右边所有元素的乘积
3. 组合 → 左右乘积相乘得到除自身以外的乘积

时间复杂度：O(n) 空间复杂度：O(n)（可优化成 O(1) 空间，通过直接在结果数组里做前缀和后缀乘积）

优化版

var productExceptSelf = function (nums) {
  const n = nums.length;
  const suf = Array(n);
  suf[n - 1] = 1;
  //初始化后缀数组，suf[i] 将被设置为 nums[i+1] * nums[i+2] * ... * nums[n-1]。末尾元素右侧没有元素，所以 suf[n-1] = 1。
  for (let i = n - 2; i >= 0; i--) {
    suf[i] = suf[i + 1] * nums[i + 1];
    //从右向左构建后缀乘积。构建结束后 suf[i] = 右侧所有元素乘积。
  }

  let pre = 1;
  //pre 保存当前索引左侧元素的乘积，初始为 1（左侧没有元素）。
  for (let i = 0; i < n; i++) {
    // 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
    suf[i] *= pre;
    pre *= nums[i];
  }

  return suf;
};

手算示例 1（无 0）

nums = [1, 2, 3, 4]，n = 4

• 构建后缀 suf：
  • suf[3] = 1
  • suf[2] = suf[3] _ nums[3] = 1 _ 4 = 4
  • suf[1] = 4 * 3 = 12
  • suf[0] = 12 * 2 = 24 -> suf = [24, 12, 4, 1]
• 用 pre 合并：
  • pre = 1 i=0: suf[0] _= pre → 24 _ 1 = 24; pre _= nums[0] → pre = 1 i=1: suf[1] _= pre → 12 _ 1 = 12; pre _= 2 → pre = 2 i=2: suf[2] _= pre → 4 _ 2 = 8; pre _= 3 → pre = 6 i=3: suf[3] _= pre → 1 _ 6 = 6; pre _= 4 → pre = 24 -> 返回 [24, 12, 8, 6]（正确）

复杂度

• 时间复杂度：O(n)（两次线性遍历：一次构建后缀，一次合并）。
• 空间复杂度：
  • 如果把返回数组 suf 计作额外空间，则为 O(n)（这是必要的输出空间）。
  • 常见的衡量方式（不计输出所需）下，这个实现只用一个额外标量 pre，因此是 O(1) 额外空间 —— 这就是该方案的优点

图解

因为第一个数的前面是空的，所以设置他的前缀积为1，后缀积同理

优化版图解

链表

160.相交链表easy

双指针解法

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  let p = headA,
    q = headB;
  while (p !== q) {
    //只有当 p 和 q 指向的节点不同时才继续走
    p = p ? p.next : headB;
    q = q ? q.next : headA;
  }
  return p;
};

用两个指针分别在两条链表上走，当一个指针走到末尾时跳到另一条链表的头继续走。这样两指针会在同一步数内经过相同的节点数：要么在交点相遇，要么同时到达 null（表示无交点）。

边界情况

• 若任一链表为空，函数会直接返回 null（因为循环会在第一次比较时发现 p === q === null? 实际上一开始若 headA 或 headB 为 null，指针会按逻辑处理，最终返回 null）。
• 如果交点就是头节点（两链表头即相同引用），一开始 p===q，直接返回头。
• 比较是基于节点引用（===），不是节点值。

模拟举例演示流程

链表情况

• A: 1 → 2 → 7 → 8 → 9
• B: 4 → 5 → 6 → 7 → 8 → 9 交点是 节点 7。

设：

• a = 2（链表 A 独有部分：1,2）
• b = 3（链表 B 独有部分：4,5,6）
• c = 3（公共部分：7,8,9）

---

指针移动过程（p 从 A，q 从 B 开始）

步数	p 所在位置	q 所在位置
0	1	4
1	2	5
2	7 (交点)	6
3	8	7 (交点)
4	9	8
5	null	9
6	4 (切到 B)	null
7	5	1 (切到 A)
8	6	2
9	7 (交点)	7 (交点) 相遇了

---

关键点

• 第 9 步的时候，p 和 q 同时到达节点 7。
• 这就是算法保证的结果：走完两条链表的“独占部分 + 公共部分”后，两者会在交点对齐。

哈希表（记录访问过的节点）

把链表 A 的所有节点引用放入 Set，然后遍历 B，找到第一个在 set 中的节点即交点。

优点：实现简单直观；缺点：额外空间 O(m)（或 O(n)）。

function getIntersectionNode_hash(headA, headB) {
  const seen = new Set(); // 用来存放链表 A 的所有节点（**节点引用**）
  let p = headA;
  while (p) {
    // 遍历链表 A，把每个节点对象放进集合
    seen.add(p);
    p = p.next;
  }

  let q = headB;
  while (q) {
    // 遍历链表 B，遇到第一个出现在集合里的节点就返回
    if (seen.has(q)) return q; // 判断是用节点引用而不是节点值
    q = q.next;
  }
  return null; // 遍历完 B 也没命中 -> 无交点
}

为什么用 Set 而不用 Map？

• 你这里只需要判断“有没有见过某个节点”（membership check）。Set 专门用于集合/成员判断，语义清晰：add + has。
• Map 是键值对结构（key → value）。如果只是想记录“见过/没见过”，用 Map 存 map.set(node, true)，再 map.has(node)，功能上能做同样的事，但多了一层无意义的 value，语义上不如 Set 直观。
• 两者在 JS 中对对象键/集合元素的比较都是基于引用（对象以引用为键），因此行为上是等价的。但 Set 更轻量、可读、更符合需求

链表结构：

• A: 1 → 2 → 7 → 8 → 9
• B: 4 → 5 → 6 → 7 → 8 → 9 交点：节点 7

---

第一阶段：遍历链表 A，把节点放进 Set

初始化：

seen = {}
p = 1

遍历过程：

步数	p 指向	操作	seen 内容（存放节点引用）
1	1	seen.add(1)
2	2	seen.add(2)
3	7	seen.add(7)
4	8	seen.add(8)
5	9	seen.add(9)
6	null	停止

此时 seen 里存放了 链表 A 的全部节点引用。

---

第二阶段：遍历链表 B，检查是否在 Set 中

初始化：

q = 4

遍历过程：

步数	q 指向	检查 seen.has(q)?	结果
1	4	seen.has(4)? 否	继续
2	5	seen.has(5)? 否	继续
3	6	seen.has(6)? 否	继续
4	7	seen.has(7)? ✅ 是	找到交点

---

直观图解

第一阶段（记录 A 的节点）：

A: 1 → 2 → 7 → 8 → 9
seen = {1, 2, 7, 8, 9}

第二阶段（走 B，逐一查找）：

B: 4 → 5 → 6 → 7 → 8 → 9
         ↑   ↑
         否  否
             ↑ 命中（7 在 seen 里）

---

总结

• 遍历 A，把所有节点引用丢进 Set。
• 遍历 B，第一个出现在 Set 里的节点就是交点。
• 在这个例子里，答案是 节点 7。

206.反转链表easy

递归（尾插法）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 首先「递」到链表末尾，把末尾节点作为新链表的头节点 revHead
// 然后在「归」的过程中，把经过的节点依次插在新链表的末尾（尾插法）
var reverseList = function(head) {
    // 判断 head === null 是为了兼容一开始链表就是空的情况
    if (head === null || head.next === null) {
        return head; // 链表末尾，即下面的 revHead
    }
    const revHead = reverseList(head.next);
    head是当前的指向，然后遇到这一行之后，一层层往下走，一直走到最后一个节点
  // 「递」到链表末尾，拿到新链表的头节点 // 反转 head.next 开始的子链表，返回新头
    const tail = head.next;
    // 在「归」的过程中，head.next 就是新链表的末尾
    // 现在的 tail 是“原来的 head.next”，它在反转后成了尾巴
    tail.next = head; // 把 head 插在新链表的末尾
    // 把 head 接到尾巴后面，等价于 head.next.next = head
    head.next = null; // 如果不写这行，新链表的末尾两个节点成环，这俩节点互相指向对方
    // 断开 head 原来的 next，避免形成环
    return revHead;
     // 整条链表的新头就是子问题返回的 revHead
};

目标：把 head -> ... -> null 变成 revHead -> ... -> head -> null

策略（自顶向下理解）：

1. 先把 head.next 开始的子链表整段反转，拿到它的新头 revHead。
2. 这时 head.next 指向的节点已经成为“子链表的尾巴”（非常关键）。
3. 把 head 接到这条反转后链表的末尾，并把 head.next 置空收尾。

复杂度分析

• 时间复杂度：O(n)，其中 n 为链表节点个数。
• 空间复杂度：O(n)。递归需要 O(n) 的栈空间

迭代（头插法）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let pre = null,
    cur = head;
  while (cur) {
    const nxt = cur.next; // 1) 记住后继，避免断链
    cur.next = pre; // 2) 反转当前边：cur 指向 pre（头插到反转链表）
    pre = cur; // 3) pre 前进：新的反转链表头
    cur = nxt; // 4) cur 前进：处理下一节点
  }
  return pre; // pre 是新头（cur 已为 null）
};

关键变量与不变式

• pre：已反转好的链表的头（初始为空）。
• cur：尚未处理的当前节点（从 head 开始）。
• nxt：暂存 cur 的后继，防止断链。

循环不变式（每轮循环开始时成立）

• pre 指向一段已反转的链表（顺序已颠倒）。
• cur 指向未处理的剩余链表的头。
• 原链表里 cur 后面的指针关系尚未被破坏。

为什么要这四步、且顺序不能乱？

1. 先存 nxt：一会儿要改 cur.next，会丢失原链；不先保存会断链。
2. 再改 cur.next = pre：反转当前边，把 cur 头插到已反转段前面。
3. pre = cur：已反转段的头向前推进。
4. cur = nxt：继续处理原链的下一个节点。

常见疑问

• 有新建节点吗？ 没有，完全是原地改 .next。
• 为什么返回 pre 而不是 head？ 循环结束时 cur 为 null，pre 正好是新链表的头；变量 head 未更新，仍指向旧头。
• 空链表/单节点？ 能自然处理：空链表直接返回 null；单节点一轮后得到 node → ∅。

复杂度

• 时间：O(n)（每个节点访问并修改一次）
• 空间：O(1)（只用常数额外变量）

234.回文链表easy

1.快慢指针解法

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 876. 链表的中间结点
function middleNode(head) {
  let slow = head,
    fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

// 206. 反转链表
function reverseList(head) {
  let pre = null,
    cur = head;
  while (cur !== null) {
    const nxt = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nxt;
  }
  return pre;
}

var isPalindrome = function (head) {
  const mid = middleNode(head);
  let head2 = reverseList(mid);
  while (head2 !== null) {
    if (head.val !== head2.val) {
      // 不是回文链表
      return false;
    }
    head = head.next;
    head2 = head2.next;
  }
  return true;
};

1. 快慢指针找中点（middleNode）

• slow 每次走 1 步，fast 每次走 2 步。
• 当 fast 走到末尾（或越过末尾）时，slow 就停在“中点”。
• 偶数长度链表会返回“第二个中点”（LeetCode 876 的定义）。

例1（奇数）：1 → 2 → 3 → 2 → 1

起步:   s=1, f=1
迭代1:  s=2, f=3
迭代2:  s=3, f=1(尾) -> 下轮 fast.next 为 null，循环结束
中点 = 3

例2（偶数）：1 → 2 → 2 → 1

起步:   s=1, f=1
迭代1:  s=2(第2个结点), f=2(第3个结点)
迭代2:  s=2(第3个结点), f=null(越界) -> 结束
中点 = 右侧那个2（第二个中点）

2. 反转后半段（reverseList）

从“中点”开始，把后半段就地反转，指针不新开数组，原地换箭头。

奇数例子：1 → 2 → 3 → 2 → 1

中点在 3，反转 3 → 2 → 1 得到：

前半：1 → 2
后半(反转后头指针 head2 指向这里)：1 → 2 → 3

（注意：反转后的后半段是“从右往左”的顺序）

可视化（反转前后）：

反转前：1 → 2 → 3 → 2 → 1
                 ↑ 中点

反转后：1 → 2    1 → 2 → 3
         ↑head   ↑head2

偶数例子：1 → 2 → 2 → 1

中点在右侧 2，反转 2 → 1 得到：

前半：1 → 2
后半(反转后)：1 → 2
head = 1, head2 = 1

3. 前后同时比较

把一个指针放在链表头（head），另一个指针放在反转后的后半段头（head2），同步向右走：

• 若某一步 head.val !== head2.val → 不是回文，返回 false。
• 若 head2 先走到 null（后半段走完了都没不等）→ 是回文，返回 true。

奇数例（1 2 3 2 1）比较过程

head:  1 → 2 → 3 → 2 → 1
head2: 1 → 2 → 3

对比：
1 == 1  ✓
2 == 2  ✓
3 == 3  ✓
(head2 到末尾) → 回文

偶数例（1 2 2 1）比较过程

head:  1 → 2 → 2 → 1
head2: 1 → 2

对比：
1 == 1  ✓
2 == 2  ✓
(head2 到末尾) → 回文

注意会断成两个链表

1. 原链表

1 → 2 → 3 → 2 → 1 → null

这里：

• 第一个 2.next = 3
• 中点 3.next = 2 所以从头出发一路能走到尾。

---

2. 开始反转（从 mid=3 开始）

第一步循环：

cur = 3, pre = null
nxt = cur.next (也就是 2)
cur.next = pre   // 3.next = null

结果：

1 → 2    3 → null
        ↑cur

此时：

• 前半段还是 1→2
• 但是“中点”这个结点的 next 已经被改了：3.next = null

也就是说：

• 2 还是指向 3（没动）
• 3 已经不再指向 2，而是指向 null

2.数组解法

把链表的所有节点值按顺序丢进数组，然后用数组的左右双指针比较，发现不相等就不是回文，全部相等就是回文。

const isPalindrome = (head) => {
  const vals = [];
  // 用 cur 遍历，避免让 head 名字被覆盖（可读性更好）
  let cur = head;
  while (cur) {
    // 第一次遍历：把链表值依次放到数组里
    vals.push(cur.val);
    cur = cur.next;
  }

  // 双指针在数组上比较
  let start = 0,
    end = vals.length - 1;
  while (start < end) {
    if (vals[start] !== vals[end]) {
      // 推荐用严格相等（!==）
      return false;
    }
    start++;
    end--;
  }
  return true; // 全都匹配，说明是回文
};

复杂度

• 时间复杂度：O(n) —— 遍历一次链表 O(n)，数组比较最多 O(n/2) → 合并 O(n)。
• 空间复杂度：O(n) —— 需要额外数组存储所有节点值。

141.环形链表easy

注意：代码比较两个节点的时候，比较的是内存地址是否一致，并没有比较节点的 val。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let slow = head,
    fast = head; // 乌龟和兔子同时从起点出发
  while (fast && fast.next) {
    //// 保证 fast.next.next 不会在此时发生空引用错误
    slow = slow.next; // 乌龟走一步
    fast = fast.next.next; // 兔子走两步
    if (fast === slow) {
      // 兔子追上乌龟（套圈），说明有环  引用相等（同一个节点）
      return true;
    }
  }
  return false; // 访问到了链表末尾，无环
};

用 === 比较节点（引用相等），不能比较 val（值相等并不能说明是同一个节点）

复杂度

• 时间复杂度：O(n)，n 为链表总节点数（非环部分 + 环长度）。因为慢指针最多走 O(μ + λ)，而 μ + λ ≤ n。
• 空间复杂度：O(1)，只用了常数个指针

常见变体：返回入环节点（而不是布尔）

通常我们还想找到环的入口节点。方法是在相遇后把一个指针重置到 head，另一个留在相遇点，然后两指针都每次走一步，最终会在入环节点相遇。代码如下：

// 返回入环节点（没有环返回 null）
var detectCycle = function (head) {
  let slow = head,
    fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // 找到相遇点后，重置一个指针到 head
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p; // p (或 slow) 就是入环节点
    }
  }
  return null;
};

142.环形链表2

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let slow = head,
    fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast === slow) {
      // 相遇
      //复用head变量
      while (slow !== head) {
        // 再走 a 步
        slow = slow.next;
        head = head.next;
      }
      return slow;
    }
  }
  return null;
};

当快慢指针第一次相遇后，设：

• 链表头到环入口的长度为 a
• 环入口到相遇点的长度为 b
• 环的剩余长度为 c，所以环总长为 b + c

数学原理：

• 快指针走的距离 = 慢指针走的距离 × 2
• 快指针走的距离 = a + n(b+c) + b
• 慢指针走的距离 = a + b
• 推导：2(a+b) = a+b+n(b+c) → a = n(b+c) - b = c + (n-1)(b+c)
• 所以从头节点 head 和相遇点 slow 同步走，每次走一步，最终会在环入口相遇。

因此 while (slow !== head) 循环的作用就是 找环入口。

算法总结

• 时间复杂度：O(n)，慢指针和快指针最多走两倍链表长度。
• 空间复杂度：O(1)，只用两个指针，不额外占用空间。
• 关键点：
  1. 使用快慢指针判断环。
  2. 第一次相遇后，再用头指针同步走来找环入口。
  3. 判断环的条件必须用 引用比较

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  // 快慢指针初始化指向 head
  let slow = head;
  let fast = head;
  // 快指针走到末尾时停止
  while (fast && fast.next) {
    // 慢指针走一步，快指针走两步
    slow = slow.next;
    fast = fast.next.next;
    // 快慢指针相遇，说明含有环
    if (slow == fast) {
      // 任一一节点指向头节点
      fast = head;
      // 同步向前进
      while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
      }
      // 返回入口节点
      return fast;
    }
  }
  // 不包含环
  return null;
};

21.合并两个有序链表easy

递归法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  //比较l1和l2，谁小，谁就是合并后链表的第一个节点
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

详细示例

假设：

l1: 1 → 3 → 5
l2: 2 → 4 → 6

第一次调用：

• 比较 1 和 2 → 1 < 2
• l1.next = mergeTwoLists(l1.next, l2) → 递归处理 3 → 5 和 2 → 4 → 6

第二次调用：

• 比较 3 和 2 → 3 > 2
• l2.next = mergeTwoLists(l1, l2.next) → 递归处理 3 → 5 和 4 → 6

第三次调用：

• 比较 3 和 4 → 3 < 4
• l1.next = mergeTwoLists(l1.next, l2) → 递归处理 5 和 4 → 6

第四次调用：

• 比较 5 和 4 → 5 > 4
• l2.next = mergeTwoLists(l1, l2.next) → 递归处理 5 和 6

第五次调用：

• 比较 5 和 6 → 5 < 6
• l1.next = mergeTwoLists(l1.next, l2) → 递归处理 null 和 6

第六次调用（终止条件）：

• l1 = null → 返回 l2 → 6

回溯结果：

• 第五次调用返回 5 → 6
• 第四次调用返回 4 → 5 → 6
• 第三次调用返回 3 → 4 → 5 → 6
• 第二次调用返回 2 → 3 → 4 → 5 → 6
• 第一次调用返回 1 → 2 → 3 → 4 → 5 → 6

---

4. 递归思路总结

• 递归选择最小节点作为当前节点
• 将剩下的链表继续合并
• 终止条件：任意一个链表为空

---

5. 时间复杂度和空间复杂度

• 时间复杂度：O(m + n) 遍历每个节点一次。
• 空间复杂度：O(m + n) 递归调用栈占用空间，每个节点会调用一次递归。

递归与回溯

---

1. 递归是“压栈再回溯”

每次调用 mergeTwoLists(l1, l2) 都会压入调用栈：

调用栈（最顶是当前正在执行的函数）：

mergeTwoLists(1→3→5, 2→4→6)   // 第1层
mergeTwoLists(3→5, 2→4→6)      // 第2层
mergeTwoLists(3→5, 4→6)        // 第3层
mergeTwoLists(5, 4→6)          // 第4层
mergeTwoLists(5, 6)             // 第5层
mergeTwoLists(null, 6)          // 第6层（终止条件）

---

2. 终止条件返回

当 l1 === null 时：

if(l1 === null) return l2;

• 这里返回了 l2（即 6）给上一层函数。
• 这一返回值就是上一层的 mergeTwoLists(l1.next, l2) 的结果。

---

3. 回溯连接

以第五次调用为例：

mergeTwoLists(5, 6)

• 比较 5 和 6 → 5 < 6
• 执行：

l1.next = mergeTwoLists(l1.next, l2) // l1.next = mergeTwoLists(null, 6)

• mergeTwoLists(null, 6) 返回 6，所以：

l1.next = 6

• 然后执行：

return l1 // 返回 5→6

这一返回值（5→6）就会被上一层接收：

mergeTwoLists(5, 4→6)  // l2.next = mergeTwoLists(5, 6)

• 上一层比较 5 和 4 → 5 > 4
• 执行：

l2.next = mergeTwoLists(l1, l2.next) // l2.next = 5→6

• l2 是 4 →?
• 所以现在：

4 → 5 → 6

• 然后 return l2 → 返回 4→5→6

---

4. 每层的 return 是谁执行的？

• 当递归函数调用内部的 mergeTwoLists(...) 返回时，上一层的代码就继续执行：

l1.next = mergeTwoLists(l1.next, l2);
return l1;

• 关键点：
  1. mergeTwoLists(...) 返回一个链表头（比如 5→6）。
  2. 将这个返回值赋值给当前层节点的 .next。
  3. 再 return 当前层节点自己（例如 4 或 5）。
• 这就形成了回溯时的“链表连接”。

---

5. 总结

• 递归深入：只比较当前节点，不修改节点的 next（还没回溯）。
• 终止条件：返回非空链表头。
• 回溯：
  1. 上层把返回的链表头赋给自己的 .next。
  2. 再返回自己作为新的链表头。
• 整个链表就被逐层拼接起来。

迭代法 简单

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  const dummy = new ListNode(); // 用哨兵节点简化代码逻辑
  let cur = dummy; // cur 指向新链表的末尾
  while (list1 && list2) {
    if (list1.val < list2.val) {
      cur.next = list1; // // 把 list1 当前节点接到新链表末尾
      list1 = list1.next;
      // list1 向后移动
    } else {
      // 注：相等的情况加哪个节点都是可以的
      cur.next = list2; // 把 list2 加到新链表中
      list2 = list2.next;
      // list2 向后移动
    }
    cur = cur.next;
    // cur 移动到新链表末尾
  }
  cur.next = list1 ?? list2; // 拼接剩余链表
  return dummy.next;
};

cur.next = list1 ?? list2; // 拼接剩余链表

原因：

• 当 while 结束时，至少有一个链表已经为空。
• 另一个非空链表剩下的部分本身就是有序的。
• 可以直接接到新链表尾部。

?? 运算符：如果 list1 不为 null，就用 list1，否则用 list2。

空间和时间复杂度

• 时间复杂度：O(m + n) 遍历每个节点一次。
• 空间复杂度：O(1) 没有递归栈，直接在原节点上修改 next。

哨兵节点

• 哨兵节点就是一个 辅助节点，通常不存储有效数据，只是用来 简化链表操作。
• 在代码中：

const dummy = new ListNode(); // 哨兵节点

• 它本身的 val 通常可以忽略（或者设置成任意值），关键是它的 next 会指向真正的链表头。

使用哨兵节点的

1. 统一处理链表插入

   • 不需要区分“头节点”或“非头节点”，所有节点都可以用同一套逻辑插入。

2. 简化返回值

   • 哨兵节点的 next 永远指向真实链表头：

   return dummy.next;

   • 无论链表有没有元素，返回方式一致，不需要特殊处理。

3. 便于迭代操作

   • 在迭代或合并链表时，cur 指针总是指向最后一个节点，插入操作统一：

   cur.next = list1; // 直接追加
   cur = cur.next;

2.两数相加

递归法

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
// l1 和 l2 为当前遍历的节点，carry 为进位
var addTwoNumbers = function (l1, l2, carry = 0) {
  if (l1 === null && l2 === null && carry === 0) {
    // 当两条链都遍历完且没有进位，递归终止，返回 null（表示没有更多节点）。
    return null;
  }

  let s = carry;
  //累加当前位的两个节点值和来自上一位的进位
  if (l1) {
    s += l1.val; // 累加进位与节点值
    l1 = l1.next;
  }
  if (l2) {
    s += l2.val;
    l2 = l2.next;
  }

  // s 除以 10 的余数为当前节点值，商为进位
  return new ListNode(s % 10, addTwoNumbers(l1, l2, Math.floor(s / 10)));
};
//Math.floor(s / 10) 是要传给下一层递归的进位（0 或 1

每次把两个节点值 l 1 .val, l 2 .val 与进位值 carry 相加，除以 10 的余数即为当前节点需要保存的数位，除以 10 的商即为新的进位值

new ListNode(..., addTwoNumbers(...))：递归调用产生 next 子链表，然后构造当前节点并把 next 指向子链表。注意 JavaScript 在创建对象前会先计算参数，所以递归会先深入到底再从底向上构建节点（即递归“完成子问题”后再创建当前节点并返回）。

复杂度

• 时间复杂度：O(max(n, m))（n、m 分别为两条链表长度），每个位只处理一次。
• 空间复杂度（结果）：O(max(n, m))（返回的新链表占用）。
• 额外空间（递归调用栈）：O(max(n, m)) —— 这是递归解的一个缺点：若链很长可能导致栈溢出（JS 环境通常没有尾递归优化）。

执行举例

输入

• l1 = [2 → 4 → 3] 代表 342
• l2 = [5 → 6 → 4] 代表 465
• 期望结果 807 → [7 → 0 → 8]

---

递归执行过程

call1（处理个位）

• l1.val = 2，l2.val = 5，carry = 0
• 算式：2 + 5 + 0 = 7
• 当前节点值 = 7，进位 = 0
• 所以要建节点：new ListNode(7, addTwoNumbers(l1.next, l2.next, 0))
• 也就是说：先记住 7，但是还得去算下一位（十位），所以递归下去 → 进入 call2

---

call2（处理十位）

• l1.val = 4，l2.val = 6，carry = 0
• 算式：4 + 6 + 0 = 10
• 当前节点值 = 0，进位 = 1
• 要建节点：new ListNode(0, addTwoNumbers(l1.next, l2.next, 1))
• 先记住 0，带着进位 1 递归下去 → 进入 call3

---

call3（处理百位）

• l1.val = 3，l2.val = 4，carry = 1
• 算式：3 + 4 + 1 = 8
• 当前节点值 = 8，进位 = 0
• 要建节点：new ListNode(8, addTwoNumbers(null, null, 0))
• 先记住 8，然后递归下去 → 进入 call4

---

call4（递归结束）

• l1 = null，l2 = null，carry = 0
• 意味着没有数字了，也没有进位
• 返回 null

---

递归“往回走”（拼接链表）

• call4 返回：null
• call3 拿到 null → 创建 new ListNode(8, null) → 相当于链表 8
• call2 拿到 8 → 创建 new ListNode(0, new ListNode(8, null)) → 链表变成 0 → 8
• call1 拿到 0 → 8 → 创建 new ListNode(7, new ListNode(0, new ListNode(8, null))) → 链表最终 7 → 0 → 8

---

最终结果

链表：[7 → 0 → 8]

迭代法

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const dummy = new ListNode();
  //new ListNode() 相当于 new ListNode(0, null)。
  // 哨兵节点
  let cur = dummy;
  let carry = 0; // 进位
  while (l1 || l2 || carry) {
    if (l1) {
      carry += l1.val; // 节点值和进位加在一起
      l1 = l1.next; // 下一个节点
    }
    if (l2) {
      carry += l2.val; // 节点值和进位加在一起
      l2 = l2.next; // 下一个节点
    }
    cur = cur.next = new ListNode(carry % 10); // 每个节点保存一个数位
    carry = Math.floor(carry / 10); // 新的进位
  }
  return dummy.next; // 哨兵节点的下一个节点就是头节点 因为 dummy 自己是个伪节点
};

cur = cur.next = new ListNode(carry % 10); 这是个紧凑写法，等价于下面两步：

const node = new ListNode(carry % 10);
cur.next = node;
cur = node;

JavaScript 的赋值表达式会返回右边的值，因此先创建新的节点（new ListNode(...)），把它赋给 cur.next，赋值表达式的结果是这个新节点，随后再把它赋给 cur，即同时完成“接入链表”和“移动尾指针”两件事。

复杂度

• 时间复杂度：O(max(n, m))（n, m 为两链长度）
• 空间复杂度（返回的链表）：O(max(n, m))；额外常数空间 O(1)（不计结果）

19.删除链表的倒数第n个节点

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  // 由于可能会删除链表头部，用哨兵节点简化代码
  const dummy = new ListNode(0, head);
  let left = dummy;
  let right = dummy;
  while (n--) {
    right = right.next; // 右指针先向右走 n 步
  }
  while (right.next) {
    left = left.next;
    right = right.next; // 左右指针一起走
  }
  //直到right走到末尾
  left.next = left.next.next; // 左指针的下一个节点就是倒数第 n 个节点  跳过要删除的那个节点
  return dummy.next;
};

思路概览

1. 创建一个哨兵（dummy），指向 head，这样即使要删的是头结点也能统一处理。
2. 让两个指针 left 和 right 都指向 dummy。
3. 先把 right 向右移动 n 步，这样 left 和 right 之间相隔 n 个节点。
4. 同时移动 left 和 right（每次都向右走一步），直到 right.next === null（right 到达最后一个节点）。
5. 此时 left.next 就是要删除的节点，把它跳过：left.next = left.next.next。
6. 返回 dummy.next（新的头）

逐步演示（例子）

链表：1 → 2 → 3 → 4 → 5，n = 2（目标：删 4）

初始：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
 left
 right

第一步：让 right 先走 n 步（循环 while (n--) right = right.next;） 走 1 步后：right 指向 1 走 2 步后：right 指向 2

现在：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
 left         right

第二步：同时向右走直到 right.next === null：

• 1st move: left -> 1, right -> 3
• 2nd move: left -> 2, right -> 4
• 3rd move: left -> 3, right -> 5 （此时 right.next === null，循环结束）

结束时：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
               left  right

left.next 是 4，正是倒数第 2 个节点。执行 left.next = left.next.next 后，4 被跳过，链表变为 1→2→3→5。返回 dummy.next（即 1）。

复杂度

• 时间复杂度：O(L)（只遍历了一次链表）
• 空间复杂度：O(1)（常数额外指针）

22.两两交换链表中的节点

迭代法

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  const dummy = new ListNode(0, head); // 哨兵：方便处理头结点被替换的情况
  let node0 = dummy; // node0 指向交换对的前驱
  let node1 = head; // node1 指向当前对的第一个节点
  while (node1 && node1.next) {
    // 至少要有两个节点才能交换
    const node2 = node1.next; // 保存第二个节点
    const node3 = node2.next; // 保存第二个节点之后的节点（可能为 null）

    node0.next = node2; // 前驱连到第二个节点（把第二个节点接到前面）
    node2.next = node1; // 第二个节点指向第一个节点（完成翻转）
    node1.next = node3; // 第一个节点接回剩余链表（保持链表连通）

    node0 = node1; // 为下一轮，前驱移动到已交换对的右端（旧的 node1）
    node1 = node3; // 下一轮的第一个节点是原来第二节点之后的 node3
  }
  return dummy.next; // 返回新的头
};

举例演示（1→2→3→4→5）

初始：

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
node0=dummy, node1=1, node2=2, node3=3

执行三步：

1. node0.next = node2：dummy -> 2
2. node2.next = node1：2 -> 1
3. node1.next = node3：1 -> 3

链表变为：

dummy -> 2 -> 1 -> 3 -> 4 -> 5

移动指针：

node0 = 1, node1 = 3

下一轮交换 3 和 4 后得到：

dummy -> 2 -> 1 -> 4 -> 3 -> 5

最后 node1 = 5（没有 node1.next），循环结束，返回 dummy.next：2 -> 1 -> 4 -> 3 -> 5。

---

复杂度

• 时间复杂度：O(n)，每个节点被访问常数次。
• 空间复杂度：O(1)，原地修改（只用额外指针，不开新节点结构，除了哨兵是常数）。

递归法

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  if (head === null || head.next === null) {
    // 基本情况：空链表或只有 1 个节点，无需交换
    return head;
  }

  const node1 = head; // 当前对的第一个节点（例如 1）
  const node2 = head.next; // 当前对的第二个节点（例如 2）
  const node3 = node2.next; // 剩余链表的头（从第三个节点开始）

  node1.next = swapPairs(node3); // 递归：把剩余链表（从 node3 开始）两两交换，返回新头，接到 node1 后面
  node2.next = node1; // 把 node2 指向 node1：完成当前对的交换

  return node2; // 返回当前段交换后的头（即原来的 node2）
};

调用栈示例（链表 1→2→3→4→5）

调用流程（缩进表示调用层级）：

swapPairs(1)
  node1=1, node2=2, node3=3
  node1.next = swapPairs(3)
    swapPairs(3)
      node1=3, node2=4, node3=5
      node1.next = swapPairs(5)
        swapPairs(5)
          head.next === null -> return 5
      node1.next = 5         // 3 -> 5
      node2.next = node1     // 4 -> 3
      return 4               // 返回子链表头 4 -> 3 -> 5
  node1.next = (返回的 4)   // 1 -> 4 -> 3 -> 5
  node2.next = node1       // 2 -> 1 -> 4 -> 3 -> 5
  return 2                 // 最终头 2 -> 1 -> 4 -> 3 -> 5

最终链表：2 → 1 → 4 → 3 → 5。

复杂度

• 时间复杂度：O(n) —— 每个节点被访问常数次。
• 空间复杂度：递归栈为 O(n)（更准确地讲，大约 O(n/2) 层递归，因为每次递归跳过两个节点，但仍是线性复杂度）。 → 若链表非常长，递归可能导致栈溢出；在这种场景下建议使用迭代版本（常数额外空间 O(1)）。

138.随机链表的复制

什么是深拷贝（Deep Copy）？

• 浅拷贝（Shallow Copy）：只是把对象的“引用”复制一份，新旧对象其实指向同一块内存。改一个，另一个也会跟着变。
• 深拷贝（Deep Copy）：真正开辟新的内存，复制一份一模一样的对象，新旧对象完全独立，互不影响。

解法

把每个复制节点插到对应原节点后面（交错链表），利用这个结构把复制节点的 random 指向设置好，最后再把交错链表拆成原链表和复制链表两条独立链表。

算法分三步（每步一遍链表）：

1. 复制每个节点并插到原节点之后：A -> A' -> B -> B' -> ...
2. 设置每个复制节点的 random：A'.random = A.random.next（因为 A.random.next 就是对应的复制节点）
3. 把链表拆分成原链表和复制链表，并恢复原链表的 next

代码

/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function (head) {
  if (head === null) {
    return null;
  }

  // 复制每个节点，把新节点直接插到原节点的后面
  for (let cur = head; cur; cur = cur.next.next) {
    cur.next = new _Node(cur.val, cur.next, null);
  }

  // 遍历交错链表中的原链表节点
  for (let cur = head; cur; cur = cur.next.next) {
    if (cur.random) {
      // 要复制的 random 是 cur.random 的下一个节点
      cur.next.random = cur.random.next;
    }
  }

  // 把交错链表分离成两个链表
  const newHead = head.next;
  //记录复制链表的头（第一个复制节点）。
  let cur = head;
  for (; cur.next.next; cur = cur.next) {
    const copy = cur.next;
    cur.next = copy.next; // 恢复原节点的 next
    copy.next = copy.next.next; // 设置新节点的 next
  }
  cur.next = null; // 恢复原节点的 next
  return newHead;
};

复杂度

• 时间复杂度：O(n)，三次线性遍历（常数倍）
• 额外空间复杂度：O(1)（不计返回的新节点；只用了常数级别的指针），比用 Map<oldNode, newNode> 的方法节省了额外 O(n) 的空间。

代码对应步骤详解（配图示）

假设原链表是 A -> B -> C -> null，且 random 指向随意（用箭头表示）。

第 1 步：交错插入复制节点

for (let cur = head; cur; cur = cur.next.next) {
    cur.next = new _Node(cur.val, cur.next, null);
}

• 作用：对每个原节点 cur，创建 copy = new _Node(cur.val, cur.next, null) 并插入到 cur 后面（cur.next = copy，而 copy.next 指回原来的下一个节点）。

• 结果（示意）：

  A -> A' -> B -> B' -> C -> C' -> null

  其中 A'.val = A.val，但 A'.random 还没设置（为 null）。

注意：for 的 cur = cur.next.next 是安全的，因为在循环体里我们把 cur.next 改成了复制节点，而复制节点的 next 已经是原来 cur.next（下一个原节点），所以 cur.next.next 指向下一个原节点。

---

第 2 步：设置复制节点的 random

for (let cur = head; cur; cur = cur.next.next) {
    if (cur.random) {
        cur.next.random = cur.random.next;
    }
}

• 对每个原节点 cur：
  • cur.next 是它的复制节点 cur'。
  • 如果 cur.random 不为 null，那么 cur.random.next 就是 cur.random 指向的那个原节点的复制节点。
  • 因此把 cur.next.random = cur.random.next 就把复制节点的 random 指向了正确的复制对象。
• 例子：如果 B.random = A，则 B'.random = B.random.next = A'。

此步仍然只遍历原节点（通过 cur = cur.next.next 跳过复制节点）。

---

第 3 步：把交错链表拆分成两个链表

const newHead = head.next;
let cur = head;
for (; cur.next.next; cur = cur.next) {
    const copy = cur.next;
    cur.next = copy.next; // 恢复原节点的 next 指向（指向下一个原节点）
    copy.next = copy.next.next; // 设置新节点的 next（指向下一个复制节点）
}
cur.next = null; // 恢复最后一个原节点的 next（指向 null）
return newHead;

• newHead = head.next 记录复制链表的头（第一个复制节点）。
• 循环逻辑解释：
  • 循环条件 cur.next.next 保证当前 cur 不是最后一个原节点（因为最后一个原节点的 next 是复制节点，复制节点的 next 为 null）。
  • 在循环体里：
    • copy = cur.next（复制节点）
    • cur.next = copy.next 把原节点 cur 的 next 恢复到下一个原节点（跳过复制节点）
    • copy.next = copy.next.next 把复制节点 copy 的 next 指向下一个复制节点
  • 循环结束后 cur 指向最后一个原节点（因为循环在最后一个原节点时会退出），所以要做 cur.next = null 来把最后一个原节点的 next 恢复为 null。
• 最终得到两条独立链表：
  • 原链表：A -> B -> C -> null
  • 复制链表：A' -> B' -> C' -> null（且 random 都已正确指向复制链表中的节点）

map映射解法

/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function (head) {
  if (!head) return head;

  let cur = head;
  const map = new Map();
  // 第一次遍历，生成一个具有val属性的链表；
  while (cur) {
    map.set(cur, new Node(cur.val));
    cur = cur.next;
  }

  // 第二次遍历：根据 map 设置 next 和 random 指针
  cur = head;
  while (cur) {
    const copy = map.get(cur); // 新节点
    copy.next = cur.next ? map.get(cur.next) : null;
    copy.random = cur.random ? map.get(cur.random) : null;
    cur = cur.next;
  }
  return map.get(head);
};

核心思想

• 第一遍遍历：为每个原节点创建一个只含 val 的新节点 copy，并把 map.set(原节点, copy)。
• 第二遍遍历：对每个原节点 cur，通过 map.get(cur.next) 和 map.get(cur.random) 去设置 map.get(cur).next 与 map.get(cur).random。如果 cur.next / cur.random 为 null，就设置为 null。
• 返回 map.get(head)（即新链表的头）。

这个方法能正确处理任意的 random 指向（包括指向自身、跨前后节点、形成循环等），因为映射保证了每个原节点只被创建一次对应的新节点。

复杂度

• 时间复杂度：O(n)（两次线性遍历）
• 空间复杂度：O(n)（Map 存储 n 个映射）

相比“交错插入法（interleaving）”：

• Map 法代码更直观、易理解、实现更快（写代码花的时间少）
• 交错插入法空间 O(1)（不额外用 Map），但实现稍复杂一些（插入/拆分的索引逻辑更容易混淆）

选择哪个看场景：

• 竞赛或面试想要最优空间时用交错法；
• 追求清晰可靠、能处理任意复杂 random 指向时，用 Map 更稳妥

图示

第一步：第一次遍历 —— 建立映射（只复制 val）

此时我们只创建 值相同的新节点，用 map 记录「原节点 -> 新节点」的对应关系。

原节点:  A(7) ──► B(13) ──► C(11)
新节点: A'(7)   B'(13)    C'(11)
map:
  A → A'
  B → B'
  C → C'

注意：此时新节点们还没有 next 和 random，它们彼此之间完全孤立。

---

第二步：第二次遍历 —— 链接 next 和 random

我们再从头遍历原链表，对每个原节点 cur：

• map.get(cur).next = map.get(cur.next)
• map.get(cur).random = map.get(cur.random)

---

处理 A

• 原 A.next = B ⇒ A'.next = map.get(B) = B'
• 原 A.random = C ⇒ A'.random = map.get(C) = C'

A'(7) ──► B'(13)
   │
   ▼
  C'(11)

以此类推。。。

148.排序链表

归并排序法（分治）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 876. 链表的中间结点（快慢指针）
function middleNode(head) {
  let pre = head,
    slow = head,
    fast = head;
  while (fast && fast.next) {
    pre = slow; // 记录 slow 的前一个节点
    slow = slow.next;
    fast = fast.next.next;
  }
  pre.next = null; // 断开 slow 的前一个节点和 slow 的连接
  return slow;
}

//fast 每次走两步，slow 每次走一步，所以当 fast 到尾（或越界）时，slow 在中点。
//pre 始终是 slow 的前一个，用来断开左半段与右半段的连接（pre.next = null）

// 21. 合并两个有序链表（双指针）
function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(); // 用哨兵节点简化代码逻辑
  let cur = dummy; // cur 指向新链表的末尾
  while (list1 && list2) {
    if (list1.val < list2.val) {
      cur.next = list1; // 把 list1 加到新链表中
      list1 = list1.next;
    } else {
      // 注：相等的情况加哪个节点都是可以的
      cur.next = list2; // 把 list2 加到新链表中
      list2 = list2.next;
    }
    cur = cur.next;
  }
  cur.next = list1 ?? list2; // 拼接剩余链表
  return dummy.next;
}

var sortList = function (head) {
  // 如果链表为空或者只有一个节点，无需排序
  if (head === null || head.next === null) {
    return head;
  }
  // 找到中间节点 head2，并断开 head2 与其前一个节点的连接
  // 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
  let head2 = middleNode(head);
  // 分治
  head = sortList(head);
  head2 = sortList(head2);
  // 合并
  return mergeTwoLists(head, head2);
};

思路总览（归并排序）

• 分（divide）：用快慢指针把链表从中间一刀两断。
• 治（conquer）：递归分别把左右两段排好序。
• 合（merge）：用两个指针把两条有序链表线性合并为一条。

整体时间复杂度 O(n log n)，只改指针不新建节点，额外空间 O(1)（不计递归栈，递归栈是 O(log n)）。

走一遍示例：[4,2,1,3]

第一层分割

• middleNode 得到左 [4,2]，右 [1,3]。

递归排左 [4,2]

• 再劈成 [4] 与 [2]，各自已排序。
• 合并 → [2,4]。

递归排右 [1,3]

• 劈成 [1] 与 [3]，合并 → [1,3]。

最终合并

• 合并 [2,4] 与 [1,3]：
  • 1 先出 → [1]
  • 2 vs 3 → 2 → [1,2]
  • 4 vs 3 → 3 → [1,2,3]
  • 拼剩余 4 → [1,2,3,4]

复杂度分析

时间复杂度：O(nlogn)，其中 n 是链表长度。递归式 T(n)=2T(n/2)+O(n)，由主定理可得时间复杂度为 O(nlogn)。从图形上理解，递归深度是 O(logn)，每一层的链表长度之和是 O(n)。计算高为 O(logn)，底边长为 O(n) 的矩形面积，得到 O(nlogn)。 空间复杂度：O(logn)。递归需要 O(logn) 的栈开销。

归并排序（迭代） 看不懂

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 获取链表长度
//用于决定外层循环的终止（当 step >= length 时结束）。
function getListLength(head) {
  let length = 0;
  while (head) {
    length++;
    head = head.next;
  }
  return length;
}

// 分割链表
// 如果链表长度 <= size，不做任何操作，返回空节点
// 如果链表长度 > size，把链表的前 size 个节点分割出来（断开连接），并返回剩余链表的头节点
function splitList(head, size) {
  // 先找到 nextHead 的前一个节点
  let cur = head;
  for (let i = 0; i < size - 1 && cur; i++) {
    cur = cur.next;
  }

  // 如果链表长度 <= size
  if (cur === null || cur.next === null) {
    return null; // 不做任何操作，返回空节点
  }

  const nextHead = cur.next;
  cur.next = null; // 断开 nextHead 的前一个节点和 nextHead 的连接
  return nextHead;
}

// 21. 合并两个有序链表（双指针）
// 返回合并后的链表的头节点和尾节点
function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(); // 用哨兵节点简化代码逻辑
  let cur = dummy; // cur 指向新链表的末尾
  while (list1 && list2) {
    if (list1.val < list2.val) {
      cur.next = list1; // 把 list1 加到新链表中
      list1 = list1.next;
    } else {
      // 注：相等的情况加哪个节点都是可以的
      cur.next = list2; // 把 list2 加到新链表中
      list2 = list2.next;
    }
    cur = cur.next;
  }
  cur.next = list1 ?? list2; // 拼接剩余链表
  while (cur.next) {
    cur = cur.next;
  }
  // 循环结束后，cur 是合并后的链表的尾节点
  return [dummy.next, cur];
}

var sortList = function (head) {
  const length = getListLength(head); // 获取链表长度
  const dummy = new ListNode(0, head); // 用哨兵节点简化代码逻辑
  // step 为步长，即参与合并的链表长度
  for (let step = 1; step < length; step *= 2) {
    let newListTail = dummy; // 新链表的末尾
    let cur = dummy.next; // 每轮循环的起始节点
    while (cur) {
      // 从 cur 开始，分割出两段长为 step 的链表，头节点分别为 head1 和 head2
      const head1 = cur;
      const head2 = splitList(head1, step);
      cur = splitList(head2, step); // 下一轮循环的起始节点
      // 合并两段长为 step 的链表
      const [head, tail] = mergeTwoLists(head1, head2);
      // 合并后的头节点 head，插到 newListTail 的后面
      newListTail.next = head;
      newListTail = tail; // tail 现在是新链表的末尾
    }
  }
  return dummy.next;
};

例子 1：[4,2,1,3]（长度 4）

初始链表（箭头表示 next）：

dummy -> 4 -> 2 -> 1 -> 3 -> null
length = 4

外层：step = 1 （把每个节点当成长度 1 的块，两两合并）

初始化：

• newListTail = dummy
• cur = dummy.next → 指向 4

内层第 1 次循环

• head1 = cur → [4 -> 2 -> 1 -> 3]（但还没断）
• head2 = splitList(head1, 1)
  • splitList：size=1，不走循环，cur = head1（即节点 4）
  • cur.next !== null，所以 nextHead = 2，并把 cur.next = null
  • 结果：head1 被截成 [4 -> null]，head2 = [2 -> 1 -> 3]
• cur = splitList(head2, 1)
  • 同理把 head2 截成 [2 -> null]，返回 cur = 1（剩下的部分）
• 现在：
  • head1 = [4]
  • head2 = [2]
  • cur = 1（下次循环从节点 1 开始）
• 合并 head1 与 head2：mergeTwoLists([4], [2]) → 返回 [2 -> 4]，tail = 4
• 把合并段接到 newListTail：
  • newListTail.next = 2，newListTail = tail = 4
• 当前新链表（从 dummy 开始）：

dummy -> 2 -> 4 -> ...

内层第 2 次循环

• cur = 1
• head1 = cur → [1 -> 3]
• head2 = splitList(head1, 1) → 切成 head1 = [1], head2 = [3]
• cur = splitList(head2, 1) → head2 是单节点，所以返回 null
• 合并 head1 与 head2：[1] + [3] → [1 -> 3]，tail = 3
• 接上：newListTail.next = 1，newListTail = 3
• 新链表变为：

dummy -> 2 -> 4 -> 1 -> 3 -> null

内层结束（cur === null）。

外层：step = 2（把长度 2 的块两两合并）

重置：

• newListTail = dummy
• cur = dummy.next → 指向 2（现在链表是 2,4,1,3）

内层第 1 次循环（也是本轮唯一一次）

• head1 = cur → [2 -> 4 -> 1 -> 3]（暂未断）
• head2 = splitList(head1, 2)
  • 在 head1 上走 size-1 = 1 步后，cur 指向节点 4
  • nextHead = 1，断开：head1 = [2 -> 4]，head2 = [1 -> 3]
• cur = splitList(head2, 2)
  • 在 head2 上走 1 步后 cur 指向 3，cur.next === null，返回 null
• 合并 head1 与 head2：merge([2,4], [1,3]) → [1 -> 2 -> 3 -> 4]，tail = 4
• 接上：newListTail.next = 1，newListTail = 4
• 新链表：

dummy -> 1 -> 2 -> 3 -> 4 -> null

外层结束：step 变成 4，step >= length，排序完成。

最终返回 dummy.next：

1 -> 2 -> 3 -> 4 -> null

---

例子 2：[4,1,3,2,5]（长度 5，演示“剩余单节点”情形）

初始：

dummy -> 4 -> 1 -> 3 -> 2 -> 5 -> null
length = 5

step = 1

初始化：newListTail = dummy，cur = 4

循环 1

• head1 = 4
• head2 = splitList(4,1) → head1=[4], head2=[1 -> 3 -> 2 -> 5]
• cur = splitList(head2,1) → head2=[1], cur=3
• merge [4] & [1] -> [1,4], tail=4
• attach → newList = 1->4

循环 2

• cur = 3
• head1 = 3
• head2 = splitList(3,1) → head1=[3], head2=[2 -> 5]
• cur = splitList(head2,1) → head2=[2], cur=5
• merge [3] & [2] -> [2,3], tail=3
• attach → newList = 1->4->2->3

循环 3

• cur = 5
• head1 = 5
• head2 = splitList(5,1) → 由于 5 是最后一个节点，splitList 返回 null（因为 cur.next === null）
• cur = splitList(head2,1) → head2 === null，仍然返回 null
• merge [5] & null -> [5], tail=5
• attach → newList = 1->4->2->3->5 内层结束（cur === null）

现在链表变为：

1 -> 4 -> 2 -> 3 -> 5 -> null

step = 2

初始化：newListTail = dummy，cur = 1

循环 1

• head1 = 1（当前整体 1,4,2,3,5）
• head2 = splitList(head1,2)：
  • 在 head1 上走 1 步到 4，nextHead = 2，断开
  • head1 = [1,4], head2 = [2,3,5]
• cur = splitList(head2,2)：
  • 在 head2 上走 1 步到 3，nextHead = 5，断开
  • head2 = [2,3], cur = 5
• merge [1,4] & [2,3] -> [1,2,3,4], tail = 4
• attach → newList = 1->2->3->4

循环 2

• cur = 5
• head1 = 5
• head2 = splitList(5,2) → splitList 在一次迭代里把 cur 变为 null（因为没有足够节点），所以返回 null
• cur = splitList(head2,2) → 仍然 null
• merge [5], null -> [5], tail = 5
• attach → newList = 1->2->3->4->5

结束内层，链表变为 1,2,3,4,5。

step = 4

• step = 4 < length(5)，再跑一轮，最终把 [1,2,3,4] 与 [5] 合并成完整有序链表 1,2,3,4,5（过程类似上面），step 翻倍到 8 >= length，结束。

最终返回：

1 -> 2 -> 3 -> 4 -> 5 -> null

146.LRU缓存

代码

class Node {
  constructor(key = 0, value = 0) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.dummy = new Node(); // 哨兵节点
    this.dummy.prev = this.dummy;
    this.dummy.next = this.dummy;
    //空链表时，哨兵的 prev/next 都指向自己，形成循环。
    this.keyToNode = new Map();
    //存储 key -> node，用于 O(1) 找到节点对象（以便快速移动或更新值）。
  }

  // 获取 key 对应的节点，同时把该节点移到链表头部
  #getNode(key) {
    if (!this.keyToNode.has(key)) {
      // 没有这本书
      return null;
    }
    const node = this.keyToNode.get(key); // 有这本书
    this.#remove(node); // 把这本书抽出来
    this.#pushFront(node); // 放到最上面
    return node;
  }

  get(key) {
    const node = this.#getNode(key); // getNode 会把对应节点移到链表头部
    return node ? node.value : -1;
  }

  put(key, value) {
    let node = this.#getNode(key); // getNode 会把对应节点移到链表头部
    if (node) {
      // 有这本书
      node.value = value; // 更新 value
      return;
    }
    //key不存在
    node = new Node(key, value); // 新书
    this.keyToNode.set(key, node); //放入map
    this.#pushFront(node); // 放到最上面
    if (this.keyToNode.size > this.capacity) {
      // 书太多了
      const backNode = this.dummy.prev;
      this.keyToNode.delete(backNode.key);
      this.#remove(backNode); // 去掉最后一本书
    }
  }

  // 删除一个节点（抽出一本书）
  #remove(x) {
    x.prev.next = x.next;
    x.next.prev = x.prev;
  }

  // 在链表头添加一个节点（把一本书放到最上面）
  #pushFront(x) {
    x.prev = this.dummy;
    x.next = this.dummy.next;
    x.prev.next = x;
    x.next.prev = x;
  }
}

核心思路（一句话）

用 哈希表（Map） + 双向链表（带哨兵的循环结构），Map 提供 O(1) 的键查找，链表维护访问顺序（头 = 最近使用，尾 = 最久未用），实现 get / put 的 O(1) 操作并在超容量时删除尾节点（LRU）。

时间 & 空间复杂度

• get：O(1)（Map 查找 + 常数次指针变更）
• put：O(1)（Map 插入/删除 + 常数次指针变更；可能伴随一次删除）
• 空间：O(capacity)（Map + 链表节点）

举例

初始化

• dummy.prev = dummy; dummy.next = dummy;
• Map: {}
• 链表: dummy ↔ dummy（空）

---

1. put(1, 1)

• Map 查不到 key=1 → 新建 Node(1,1)。
• #pushFront(node)：插到头
• Map: {1: Node(1,1)}
• 链表: dummy ↔ [1] ↔ dummy

---

2. put(2, 2)

• Map 查不到 key=2 → 新建 Node(2,2)。
• #pushFront 插到头。
• Map: {1,2}
• 链表: dummy ↔ [2] ↔ [1] ↔ dummy
  • [2] 是最新的（MRU）
  • [1] 是最旧的（LRU）

---

3. get(1)

• #getNode(1)：找到 Node(1,1)。
• 调用 #remove(1) + #pushFront(1) → 把 [1] 移到头。
• Map: {1,2}
• 链表: dummy ↔ [1] ↔ [2] ↔ dummy
• 返回值：1

---

4. put(3, 3)

• Map 没有 key=3 → 新建 Node(3,3)，插到头。
• Map size = 3 > capacity=2 → 删除尾节点。
• 尾节点 = dummy.prev = [2] → 删除 2。
• Map: {1,3}
• 链表: dummy ↔ [3] ↔ [1] ↔ dummy
• 现在 [3] 是最新的，[1] 是最旧的。

---

5. get(2)

• Map 没有 key=2 → 返回 -1。
• 链表保持不变。

---

6. put(4, 4)

• Map 没有 key=4 → 新建 Node(4,4)，插到头。
• Map size = 3 > 2 → 删除尾节点 [1]。
• Map: {3,4}
• 链表: dummy ↔ [4] ↔ [3] ↔ dummy

---

7. get(1)

• Map 没有 key=1 → 返回 -1

---

8. get(3)

• Map 找到 key=3 → 把 [3] 移到头。
• 链表: dummy ↔ [3] ↔ [4] ↔ dummy
• 返回值：3

---

9. get(4)

• Map 找到 key=4 → 把 [4] 移到头。
• 链表: dummy ↔ [4] ↔ [3] ↔ dummy
• 返回值：4

---

最终状态

• Map: {3,4}
• 链表: dummy ↔ [4] ↔ [3] ↔ dummy
• 输出顺序：
  • get(1) → 1
  • get(2) → -1
  • get(1) → -1
  • get(3) → 3
  • get(4) → 4

栈

20.有效的括号easy

写法一

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 如果长度是奇数，肯定无法匹配
  if (s.length % 2 !== 0) {
    return false;
  }

  // 右括号 -> 对应左括号 的映射
  const matchingPairs = {
    ")": "(",
    "]": "[",
    "}": "{",
  };

  // 栈，用于保存遇到的左括号
  const stack = [];

  for (const char of s) {
    if (!(char in matchingPairs)) {
      // 此时char是左括号
      // 遇到左括号：直接入栈
      stack.push(char);
    } else {
      // 遇到右括号：
      // 此时char是右括号
      // 1. 栈不能为空
      // 2. 栈顶元素必须和当前右括号匹配
      if (stack.length === 0 || stack.pop() !== matchingPairs[char]) {
        return false;
      }
    }
  }

  // 最终栈必须为空（所有左括号都匹配完毕）
  return stack.length === 0;
};

写法二

/**
 * 判断括号字符串是否有效
 * @param {string} s - 仅包含 ()[]{} 的字符串
 * @return {boolean} - true 表示有效括号，false 表示无效
 */
var isValid = function (s) {
  // 1. 如果长度是奇数，必定无法完全配对
  if (s.length % 2 !== 0) {
    return false;
  }

  // 2. 左括号 -> 对应的右括号映射表
  const bracketPairs = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  // 3. 栈：用于存放“期望匹配的右括号”
  const stack = [];

  // 4. 遍历字符串中的每个字符
  for (const char of s) {
    if (bracketPairs[char]) {
      // char 是左括号
      // 入栈时存放“它期望的右括号”
      stack.push(bracketPairs[char]);
    } else {
      // char 是右括号
      // 情况 1：栈为空 → 没有与之匹配的左括号
      // 情况 2：栈顶的期望右括号 ≠ 当前字符
      if (stack.length === 0 || stack.pop() !== char) {
        return false;
      }
    }
  }

  // 5. 如果栈为空，说明所有括号都正确匹配
  return stack.length === 0;
};

在哈希表/数组中保存每个左括号对应的右括号。在遍历到左括号时，把对应的右括号入栈。这样遍历到右括号时，只需看栈顶括号是否一样即可。

注意：

if (bracketPairs[char])： 用来判断 char 是否是左括号。

• 如果是左括号 → bracketPairs[char] 会得到对应右括号（真值），条件成立。
• 如果是右括号 → bracketPairs[char] 是 undefined（假值），走到 else。

写法三

/**
 * 判断括号字符串是否有效
 * @param {string} s - 输入字符串（仅包含 ()[]{}）
 * @return {boolean} - true 表示有效括号，false 表示无效
 */
var isValid = function (s) {
  // 1. 长度为奇数 → 不可能完全配对
  if (s.length % 2 !== 0) {
    return false;
  }

  // 2. 用数组模拟栈，保存“期望的右括号”
  const stack = [];

  // 3. 遍历每个字符
  for (const char of s) {
    if (char === "(") {
      stack.push(")"); // 遇到左括号 → 压入对应的右括号
    } else if (char === "[") {
      stack.push("]");
    } else if (char === "{") {
      stack.push("}");
    } else {
      // 遇到右括号
      // 情况1：栈为空 → 没有对应的左括号
      // 情况2：栈顶期望的右括号 ≠ 当前字符
      if (stack.length === 0 || stack.pop() !== char) {
        return false;
      }
    }
  }

  // 4. 最后栈必须为空，才能保证所有括号配对成功
  return stack.length === 0;
};

155.最小栈

前缀最小和

1. 什么是“前缀”

数组 nums = [5, 3, 7, 2, 6]

• 前缀 0（到索引 0 为止）：[5]
• 前缀 1（到索引 1 为止）：[5, 3]
• 前缀 2（到索引 2 为止）：[5, 3, 7]
• 前缀 3（到索引 3 为止）：[5, 3, 7, 2]
• 前缀 4（到索引 4 为止）：[5, 3, 7, 2, 6]

“前缀”就是数组从头开始到某个位置的子数组。

---

2. 前缀的最小值

对于每个前缀，找出它里面的最小数：

• 前缀 [5] → 最小值是 5
• 前缀 [5, 3] → 最小值是 3
• 前缀 [5, 3, 7] → 最小值还是 3
• 前缀 [5, 3, 7, 2] → 最小值是 2
• 前缀 [5, 3, 7, 2, 6] → 最小值还是 2

所以我们得到一个数组 preMin：

preMin = [5, 3, 3, 2, 2]

---

3. 通用公式

用公式来表示：

preMin[i] = min(nums[0], nums[1], … , nums[i])

但这样每次都要从头算，效率低。 所以我们用递推关系：

preMin[i] = min(preMin[i-1], nums[i])

也就是说：

• 到位置 i 的最小值 = 之前的最小值 和 当前元素 nums[i] 取个较小的。

class MinStack {
  constructor() {
    // 栈底哨兵：[任意值, 当前最小值]
    // 这里写 [0, Infinity]，第二项用 Infinity 作为初始的“前缀最小值”。
    // 第一个元素写成 0 / null / undefined 都可以 —— 不会把它当作真实数据读取。
    this.st = [[0, Infinity]]; // 栈底 sentinel（哨兵）
  }

  // 入栈
  push(val) {
    // 取出当前栈的最小值（栈顶 pair 的第二项），然后和 val 比较得到新的前缀最小值
    // push 到栈中的是一个 pair：[val, newMin]
    this.st.push([val, Math.min(this.getMin(), val)]);
  }

  // 出栈（题目保证不会在空栈上 pop）
  pop() {
    // 直接弹出栈顶 pair —— 包括值和它对应的前缀最小值
    this.st.pop();
  }

  // 读栈顶元素值（不弹出）
  top() {
    // 返回栈顶 pair 的第一个元素（即真实的值）
    return this.st[this.st.length - 1][0];
  }

  // 取当前栈（所有元素）的最小值
  getMin() {
    // 返回栈顶 pair 的第二个元素（即到栈顶为止的前缀最小值）
    return this.st[this.st.length - 1][1];
  }
}

实现一个能在 O(1) 时间内返回当前栈最小值的栈（MinStack）。等价于：把数组 nums 看成不断在末尾 push/pop 的栈，你要维护每个前缀的最小值 preMin[i] = min(nums[0..i])，并在 getMin() 时快速返回当前前缀最小值。

每个入栈元素不仅存它自己，还同时存「到它为止的前缀最小值」。也就是在栈里存 pair = [val, currentMin]：

• currentMin = min(previous currentMin, val)（这正是 preMin[i] = min(preMin[i-1], nums[i]) 的实现）

这样栈顶的 pair[1] 就是当前整个栈（所有元素）的最小值，getMin() 直接返回它，O(1)。

逐步演示（把栈内容在每一步都写出来）

初始状态（构造后）：

st = [[0, Infinity]]

（只有哨兵，表示“尚无真实元素，当前最小值是 +∞”）

操作序列与状态：

1. push(5)
   • newMin = min(Infinity, 5) = 5
   • st = [[0, Infinity], [5, 5]]
2. push(3)
   • newMin = min(5, 3) = 3
   • st = [[0, Inf], [5,5], [3,3]]
3. push(3)（再次推入 3，测试重复值）
   • newMin = min(3, 3) = 3
   • st = [[0,Inf], [5,5], [3,3], [3,3]]
4. push(4)
   • newMin = min(3, 4) = 3
   • st = [[0,Inf], [5,5], [3,3], [3,3], [4,3]]

现在查询：

• getMin() → 读栈顶第二项：3
• top() → 读栈顶第一项：4

接着： \5. pop()（弹出 4）

• 弹出 [4,3]
• st 恢复为 [[0,Inf], [5,5], [3,3], [3,3]]
• 此时 getMin() 仍为 3（栈顶 pair 的第二项）

1. 再 pop()（弹出一个 3）
   • st → [[0,Inf], [5,5], [3,3]]，getMin() = 3
2. 再 pop()（弹出最后一个 3）
   • st → [[0,Inf], [5,5]]，getMin() = 5

（若继续 pop() 到只剩哨兵，题目通常保证不会对空栈调用 top/getMin/pop —— 否则需要额外判断。）

为什么用哨兵（sentinel = [0, Infinity]）？

• 第一次 push(val) 要计算 Math.min(this.getMin(), val)；若没有初始值，getMin() 无处取数会出错。
• 用 Infinity 作为初始“最小值”，使第一步 min(Infinity, val) 得到 val，逻辑统一，无须在 push 里做空栈分支判断。
• 哨兵的第一个值写 0（或 null）都行，因为我们永远不会把它当作“有效数据”去 top()（题目保证不会在空栈上操作）。

复杂度

• 时间：push, pop, top, getMin —— 全部 O(1)。
• 空间：O(n) —— 每个真实元素额外保存一个当前最小值。

394.字符串解码

把形如 3[a2[c]]、2[abc]3[cd]ef 这样的编码字符串解码为普通字符串。字表示重复次数，[] 包裹要重复的子串，可以嵌套。

方法1

/**
 * @param {string} s
 * @return {string}
 */
const decodeString = (s) => {
  let numStack = []; // 存倍数的栈
  let strStack = []; // 存 待拼接的str 的栈
  // 存待拼接的字符串（对应每个 [ 之前已得到的字符串）
  let num = 0; // 倍数的“搬运工”
  // 当前读到的数字（可能多位）
  let result = ""; // 字符串的“搬运工”
  // 当前层级正在拼接的字符串
  for (const char of s) {
    // 逐字符扫描
    if (!isNaN(char)) {
      // 遇到数字
      num = num * 10 + Number(char); // 算出倍数
      // 支持多位数：例如读 "12" 时变成 12
    } else if (char == "[") {
      // 遇到 [
      strStack.push(result); // result串入栈
      result = ""; // 入栈后清零
      numStack.push(num); // 倍数num进入栈等待
      num = 0; // 入栈后清零
    } else if (char == "]") {
      // 遇到 ]，两个栈的栈顶出栈
      let repeatTimes = numStack.pop(); // 获取拷贝次数
      // 把当前层的 result 重复 repeatTimes 次，并拼回到上一层（栈顶字符串）
      result = strStack.pop() + result.repeat(repeatTimes); // 构建子串
    } else {
      result += char; // 遇到字母，追加给result串
    }
  }
  return result;
};

关键变量和思路（一句话）

用两个栈：numStack 存每个 [ 对应的重复次数，strStack 存 [ 前面已拼好的字符串；遇到 [ 时入栈保存当前状态，遇到 ] 时出栈并把当前 result 重复拼回到上层字符串。num 和 result 是当前正在构建的“搬运工”

示例 1（简单）：s = "3[a]2[bc]"

最终结果应为 "aaabcbc"。下面给出简短的过程（只列出关键变化）：

• 开始： numStack=[], strStack=[], num=0, result=''

1. 读 '3' → num=3
2. 读 '[' → push result('') 到 strStack，push num(3) 到 numStack，清 result 和 numnumStack=[3], strStack=[''], num=0, result=''
3. 读 'a' → result='a'
4. 读 ']' → pop repeatTimes=3，pop prefix=''，result = '' + 'a'.repeat(3) = 'aaa'numStack=[], strStack=[], result='aaa'
5. 读 '2' → num=2
6. 读 '[' → push result('aaa') 到 strStack，push num(2) 到 numStack，清 result 和 numnumStack=[2], strStack=['aaa'], result=''
7. 读 'b' → result='b'
8. 读 'c' → result='bc'
9. 读 ']' → pop repeatTimes=2，pop prefix='aaa'，result = 'aaa' + 'bc'.repeat(2) = 'aaabcbc' 返回 "aaabcbc"。

示例 2（嵌套详细逐字符跟踪）：s = "3[a2[c]]"

运行过程（逐字符）

1. 遇到 '3' 这是一个数字，把它存到 num，此时 num = 3。
2. 遇到 '[' 表示要开始一个新的子串：
   • 把当前的 result（现在是 ''）存入 strStack；
   • 把当前的 num（3）存入 numStack；
   • 然后清空 num 和 result，准备解析括号里面的内容。
3. 遇到 'a' 这是字母，直接加到 result，此时 result = "a"。
4. 遇到 '2' 这是数字，把它存到 num，现在 num = 2。
5. 遇到第二个 '[' 又是一个新的子串：
   • 把当前 result（"a"）压进 strStack；
   • 把 num（2）压进 numStack；
   • 清空 result 和 num，准备解析括号里面的内容。
6. 遇到 'c' 这是字母，加到 result，此时 result = "c"。
7. 遇到 ']'（第一个右括号） 表示内层子串结束：
   • 从 numStack 弹出 2，表示重复次数；
   • 从 strStack 弹出 "a"，这是之前保存的前缀；
   • 把 result（"c"）重复 2 次，得到 "cc"；
   • 拼接在前缀 "a" 后面，新的 result = "acc"。
8. 遇到最后一个 ']'（外层右括号） 表示外层子串结束：
   • 从 numStack 弹出 3，表示重复次数；
   • 从 strStack 弹出 ""（外层括号之前的前缀，是空串）；
   • 把 result（"acc"）重复 3 次，得到 "accaccacc"；
   • 拼接在前缀 "" 后面，result = "accaccacc"。

---

最终结果

返回 "accaccacc"。

解法2 不太懂

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = (s) => {
  let stack = [];
  for (const char of s) {
    if (char !== "]") {
      // ] 前的字符都入栈
      stack.push(char);
      continue;
    }
    let cur = stack.pop(); // 弹出一个来检测
    let str = ""; // 组装字符串
    // 接下来肯定是遇到字母，直到遇到 [
    while (cur !== "[") {
      str = cur + str; // cur字符加在左边
      cur = stack.pop(); // 再拉出一个
    }
    // 此时cur为 [，接下来要遇到数字
    let num = "";
    cur = stack.pop(); // 用下一个将 [ 覆盖
    while (!isNaN(cur)) {
      num = cur + num; // 数字字符加在左边
      cur = stack.pop(); // 再拉出一个
    }
    // 现在要么是字母，要么是 [
    stack.push(cur);
    stack.push(str.repeat(num));
  }
  return stack.join("");
};

示例 1（简单，不嵌套）：s = "3[a]2[bc]"（文字描述）

• 扫描并压栈直到第一个 ']'： 读 '3' '[' 'a' 时栈变成 ['3', '[', 'a']。遇到 ']'，开始处理：
  1. 弹出 'a'，str='' → str = 'a'。再弹出，得到 '['（停止构建 str）。
  2. 弹出下一个得到 '3'，因为是数字，num='3'。再弹出得到非数字（此例中栈空，弹出会是 undefined，循环结束），把该非数字（undefined）放回栈会被忽略或需要校验；但在正确输入流程中通常它是外层内容。
  3. 把 'a' 重复 3 次得到 'aaa'，压回栈。此时栈大致变为 ['aaa']（外层数字处理完，继续扫描）。
• 继续扫描 2 '[' 'b' 'c'，遇到 ']' 时栈为 ['aaa', '2','[','b','c']，处理类似步骤得到 'bc' 重复 2 次 'bcbc'，压回栈，最后 stack.join('') → 'aaabcbc'。

（注：上面提到的 undefined 在实际运行中不会出现，因为在处理数字时当栈弹空 cur 为 undefined，isNaN(undefined) 为 true，循环退出并把 undefined 放回栈会带来问题——所以实现时输入必须正确或应改成更稳健的数字检测并避免把 undefined 放进栈。）

---

示例 2（嵌套，文字逐步说明）：s = "3[a2[c]]" → 目标 "accaccacc"

按扫描顺序逐字符叙述（并说明关键时刻栈的状态）：

1. 读 '3'：压栈 → ['3']。
2. 读 '['：压栈 → ['3', '[']。
3. 读 'a'：压栈 → ['3', '[', 'a']。
4. 读 '2'：压栈 → ['3', '[', 'a', '2']。
5. 读 '['：压栈 → ['3', '[', 'a', '2', '[']。
6. 读 'c'：压栈 → ['3', '[', 'a', '2', '[', 'c']。
7. 读 ']'（遇到第一个右括号，开始处理内层 [c]2）：
   • 弹出得到 cur = 'c'，str = '' → 执行 str = cur + str 得到 str = 'c'。
   • 再弹一项得到 cur = '['，停止构建 str（此时 str === 'c'）。
   • 弹出下一个元素得到 cur = '2'，因为是数字，进入数字循环：num = '' → num = '2'，再弹一个得到 cur = 'a'（不是数字），数字循环结束。
   • 把停止读数字时得到的 cur（这里是 'a'）放回栈（属于外层内容）。
   • 将 str.repeat(num) 即 'c'.repeat(2) → 'cc' 压回栈。
   • 此刻栈变为：['3', '[', 'a', 'cc']。
8. 继续扫描，碰到外层的 ']'（处理 a 和 cc）：
   • 弹出 cur = 'cc'，str='' → str = 'cc'，再弹出 cur = 'a' → str = 'a' + 'cc' = 'acc'，再弹出得到 cur = '['（停止）。
   • 弹出下一个得到 cur = '3'，这是数字，num = '3'，再弹得到 cur = undefined（或空），数字循环结束（对正确输入来说这就是结束条件）。把 cur（非数字）放回栈（通常为空，不影响最终结果）。
   • 将 str.repeat(num) → 'acc'.repeat(3) → 'accaccacc' 压回栈。
   • 最终栈为 ['accaccacc']。

扫描结束，返回 stack.join('') → "accaccacc"。

739.每日温度

暴力解法× 会超出时间限制

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
const dailyTemperatures = (T) => {
  const res = new Array(T.length).fill(0);
  for (let i = 0; i < T.length; i++) {
    for (let j = i + 1; j < T.length; j++) {
      if (T[j] > T[i]) {
        res[i] = j - i;
        break;
      }
    }
  }
  return res;
};

单调栈解法

const dailyTemperatures = (T) => {
  const res = new Array(T.length).fill(0);
  const stack = [];
  for (let i = T.length - 1; i >= 0; i--) {
    while (stack.length && T[i] >= T[stack[stack.length - 1]]) {
      stack.pop();
    }
    if (stack.length) {
      res[i] = stack[stack.length - 1] - i;
    }
    stack.push(i);
  }
  return res;
};

对每一天 i，找出之后第一个比 T[i] 更高温度的那天，返回需要等的天数；找不到就 0。算法从右向左遍历，用单调栈（存下标）加速查找。

逐步演示（从右向左）

初始：res = [0,0,0,0,0,0,0,0]，stack = []（栈里存的是下标；为了看得清楚我也会同时写出对应温度）

• i = 7，T[7] = 73stack 为空 -> 没有更暖的一天 -> res[7] = 0 push 7 -> stack = [7(73)]
• i = 6，T[6] = 76 while：76 >= T → pop 7（因为 7 天的温度不比当前高，不能作为“更暖”候选） 现在 stack 为空 -> res[6] = 0 push 6 -> stack = [6(76)]
• i = 5，T[5] = 72 while：72 >= T? 否（72 < 76），所以栈顶 6 是第一个比 72 更暖的日子 res[5] = 6 - 5 = 1 push 5 -> stack = [6(76), 5(72)]
• i = 4，T[4] = 6969 >= T? 否 → res[4] = 5 - 4 = 1 push 4 -> stack = [6(76), 5(72), 4(69)]
• i = 3，T[3] = 7171 >= T → pop 4 现在 stack = ? 否 最近的更暖是下标 5 -> res[3] = 5 - 3 = 2 push 3 -> stack = [6(76),5(72),3(71)]
• i = 2，T[2] = 7575 >= T → pop 3 75 >= T → pop 5 现在 stack = ? 否 最近更暖是 6 -> res[2] = 6 - 2 = 4 push 2 -> stack = [6(76),2(75)]
• i = 1，T[1] = 7474 >= T? 否 → res[1] = 2 - 1 = 1 push 1 -> stack = [6(76),2(75),1(74)]
• i = 0，T[0] = 7373 >= T? 否 → res[0] = 1 - 0 = 1 push 0 -> stack = [6(76),2(75),1(74),0(73)]

最终 res = [1,1,4,2,1,1,0,0]，与期望一致。

注意

1. 栈里存下标，且维护一个“单调递减的温度序列”（从栈底到栈顶，温度是严格下降的）。因此栈顶总是当前元素右侧最近且比它温度高的候选。
2. 遍历方向：从右往左，保证当处理到 i 时，栈中只包含 i 右侧的天。
3. while (stack.length && T[i] >= T[stack[top]]) stack.pop()：把那些温度 小于等于 当前的下标都踢掉（因为它们不能作为“更暖”的答案——等于的也不算“更暖”），留下首个比当前温度高的下标（如果有）。
4. 时间复杂度 O(n)：每个下标最多被 push/pop 一次。空间复杂度 O(n)。

堆

215.数组中的第K个最大元素 第k大

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 整个流程就是上浮下沉
var findKthLargest = function (nums, k) {
  let heapSize = nums.length;
  buildMaxHeap(nums, heapSize); // 构建好了一个大顶堆
  // 进行下沉 大顶堆是最大元素下沉到末尾
  // 把最大值依次交换到末尾 k-1 次
  for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
    swap(nums, 0, i); // 把当前最大 (nums[0]) 放到末尾 i
    --heapSize; // 下沉后的元素不参与到大顶堆的调整
    // 重新调整大顶堆
    maxHeapify(nums, 0, heapSize); // 对新根下沉，恢复堆性质
  }
  return nums[0]; // 此时堆顶就是第 k 大

  // 自下而上构建一颗大顶堆
  function buildMaxHeap(nums, heapSize) {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(nums, i, heapSize);
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(nums, i, heapSize) {
    let l = i * 2 + 1;
    let r = i * 2 + 2;
    let largest = i;
    if (l < heapSize && nums[l] > nums[largest]) {
      largest = l;
    }
    if (r < heapSize && nums[r] > nums[largest]) {
      largest = r;
    }
    if (largest !== i) {
      swap(nums, i, largest); // 进行节点调整
      // 继续调整下面的非叶子节点
      maxHeapify(nums, largest, heapSize);
    }
  }
  function swap(a, i, j) {
    let temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
};

思路概述

这段代码用的是**原地大顶堆（Max-Heap）**的方法：

1. 先把数组原地建成大顶堆（根是当前剩余元素中的最大值）；
2. 然后把堆顶（最大值）与数组末尾交换，再把堆大小减 1 并对新的堆顶做下沉（maxHeapify）；
3. 重复第2步 k−1 次后，堆顶就是第 k 大的元素，直接返回 nums[0]。

叶子节点就是没有子节点的节点

347.前k个高频元素

桶排序

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  // 第一步：统计每个元素的出现次数
  const cnt = new Map();
  // key 是元素，value 是出现次数。
  for (const x of nums) {
    cnt.set(x, (cnt.get(x) ?? 0) + 1);
    // 如果 cnt.get(x) 是 undefined（还没出现过），?? 会把它当 0，然后加 1。
  }
  const maxCnt = Math.max(...cnt.values());
  //找出现次数的最大值 maxCnt，用于创建桶数组的长度。

  // 第二步：把出现次数相同的元素，放到同一个桶中
  const buckets = Array.from({ length: maxCnt + 1 }, () => []);
  //Array.from({ length: N }, () => something)：创建一个长度为 N 的数组，每个元素都是 something 的返回值。
  //每个元素是一个独立的空数组，用于存放频率相同的元素。
  //maxCnt + 1：因为我们要用数组下标来表示频率，频率范围是 1 ~ maxCnt，而数组下标是从 0 开始的。
  //例如，如果 maxCnt = 3，我们就希望有 buckets[1]、buckets[2]、buckets[3] 可以存元素。
  //因为数组下标从 0 开始，长度至少要 maxCnt + 1，这样 buckets[3] 才存在。
  for (const [x, c] of cnt.entries()) {
    buckets[c].push(x);
  }

  // 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
  const ans = [];
  // 注意题目保证答案唯一，一定会出现某次 push 后 ans.length 恰好等于 k 的情况
  for (let i = maxCnt; i >= 0 && ans.length < k; i--) {
    ans.push(...buckets[i]);
  }
  return ans;
};

复杂度分析

• 时间复杂度：O(n)（其中 n = nums.length）
  • 统计频率 O(n)
  • 建桶和遍历桶总体也是 O(n)（maxCnt ≤ n，每个元素放入桶一次）
• 空间复杂度：O(n)（Map + buckets 最坏情况都会占 O(n)）

思路概述

这是用 桶排序（bucket） 的一种常见做法来解决 “出现频率前 k 的元素” 问题。核心想法是：

1. 先统计每个数出现的次数（用 Map）。
2. 因为频率范围是 1..n（n 为数组长度），可以建立长度为 maxCnt+1 的数组 buckets，把出现次数为 c 的所有元素放到 buckets[c]。
3. 从高频往低频遍历 buckets，依次把元素加入答案，直到凑够 k 个为止。

画图

二叉树

94.二叉树的中序遍历 easy

递归法

const inorderTraversal = (root) => {
  const res = []; // 存放结果的数组
  const inorder = (root) => {
    // 递归函数
    if (root == null) {
      // 递归基：遇到空节点直接返回
      return;
    }
    inorder(root.left); // 先递归左子树
    res.push(root.val); // 再访问当前节点（把值加入结果）
    inorder(root.right); // 最后递归右子树
  };
  inorder(root); // 从根开始递归
  return res; // 返回结果数组
};

中序遍历定义（Inorder）：对每个节点，先遍历左子树，再访问当前节点（把值放到结果数组），最后遍历右子树。顺序是：左 → 根 → 右。

迭代法

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = (root) => {
  const res = [];
  const stack = [];

  while (root) {
    // 能压栈的左子节点都压进来
    stack.push(root);
    root = root.left;
  }
  while (stack.length) {
    let node = stack.pop(); // 栈顶的节点出栈
    res.push(node.val); // 在压入右子树之前，处理它的数值部分（因为中序遍历）
    node = node.right; // 获取它的右子树
    while (node) {
      // 右子树存在，执行while循环
      stack.push(node); // 压入当前root
      node = node.left; // 不断压入左子节点
    }
  }
  return res;
};

初始

• root = 1, stack = [], res = []

第一次把最左路径压进去（第一个 while）

执行 while (root)：

• push 1 → stack = [1], root = 1.left = 2
• push 2 → stack = [1,2], root = 2.left = 4
• push 4 → stack = [1,2,4], root = 4.left = null 结束初始压栈，root = null

外层循环迭代过程（每次一轮 = pop + 处理右子树左链）

1. stack = [1,2,4]pop() → node = 4，stack = [1,2]res.push(4) → res = [4]node = node.right = null → 内层 while 不执行
2. stack = [1,2]pop() → node = 2，stack = [1]res.push(2) → res = [4,2]node = node.right = 5 内层 while：push 5 → stack = [1,5]，node = 5.left = null
3. stack = [1,5]pop() → node = 5，stack = [1]res.push(5) → res = [4,2,5]node = node.right = null → 内层 while 不执行
4. stack = [1]pop() → node = 1，stack = []res.push(1) → res = [4,2,5,1]node = node.right = 3 内层 while：push 3 → stack = [3]，node = 3.left = null
5. stack = [3]pop() → node = 3，stack = []res.push(3) → res = [4,2,5,1,3]node = node.right = 6 内层 while：push 6 → stack = [6]，node = 6.left = null
6. stack = [6]pop() → node = 6，stack = []res.push(6) → res = [4,2,5,1,3,6]node = node.right = null

外层 while 结束（栈空），返回 res = [4,2,5,1,3,6]，与中序预期一致。

复杂度

• 时间：O(n) — 每个节点最多被 push 和 pop 各一次（常数次操作）。
• 空间：O(h) — 栈的最大高度等于树高度 h。最坏情况（链状） h = n，变为 O(n)。

104.二叉树的最大深度 easy

DFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxDepth = (root) => {
  if (root == null) return 0;
  const leftMaxDepth = maxDepth(root.left);
  const rightMaxDepth = maxDepth(root.right);
  return 1 + Math.max(leftMaxDepth, rightMaxDepth);
};

说明：每个 maxDepth(node) 会再去算它的 left 和 right，当遇到 null（空子树）就返回 0（这是递归终止条件）。节点的深度就是 1 + max(左子树深度, 右子树深度)。

时间/空间复杂度

• 时间复杂度：O(n) — 每个节点被访问一次（做一次 max 和加法）。
• 空间复杂度（递归栈）：O(h)，h 是树高度（在最坏情况下链式时为 O(n)）

BFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxDepth = (root) => {
    if (root == null) return 0;
    const queue = [root];
    let depth = 1;
    while (queue.length) {
        // 当前层的节点个数
        const levelSize = queue.length;
        // 逐个让当前层的节点出列
        for (let i = 0; i < levelSize; i++) {
            // 当前出列的节点
            const cur = queue.shift();
            // 左右子节点入列
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
        }
        // 当前层所有节点已经出列，如果队列不为空，说明有下一层节点，depth+1
        if (queue.length) depth++;
    }
    return depth;
};

代码逻辑回顾

• 用一个 queue 保存当前层的所有节点；
• 每次 while 循环，处理一整层；
• levelSize 记录这一层的节点数；
• 出队这些节点，同时把它们的孩子节点入队；
• 一层处理完后，如果队列里还有下一层节点，就 depth++

运行过程

初始

queue = [1]
depth = 1

---

第 1 层（根节点）

• levelSize = 1 → 处理 1 个节点
• 出队 1，入队左右孩子：2, 3

queue = [2, 3]
depth = 1 → 下一层存在 → depth = 2

---

第 2 层

• levelSize = 2 → 处理 2 个节点

处理节点 2 → 出队 → 左孩子 4 入队 处理节点 3 → 出队 → 左孩子 5，右孩子 6 入队

queue = [4, 5, 6]
depth = 2 → 下一层存在 → depth = 3

---

第 3 层

• levelSize = 3 → 处理 3 个节点

处理节点 4 → 出队（没有孩子） 处理节点 5 → 出队 → 右孩子 7 入队 处理节点 6 → 出队（没有孩子）

queue = [7]
depth = 3 → 下一层存在 → depth = 4

---

第 4 层

• levelSize = 1 → 处理 1 个节点

处理节点 7 → 出队（没有孩子）

queue = []
depth = 4 → 队列空了，循环结束

---

最终结果

return depth = 4

226.翻转二叉树 easy

DFS递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
const invertTree = (root) => {
  if (root == null) {
    // 遍历到null节点时，不用翻转，直接返回它本身
    return root;
  }
  const temp = root.left; // 暂存左子树
  root.left = root.right; // 左 <- 右
  root.right = temp; // 右 <- 原左（完成当前节点的左右交换）

  // 内部的翻转交给递归去做
  // 交换只是处理当前节点，子树的翻转交给递归：
  invertTree(root.left);
  // 递归翻转（现在）左子树（注意这是交换后的位置）
  invertTree(root.right);
  // 递归翻转（现在）右子树
  return root; // 返回翻转后的子树根
};

对每个节点：把左右子树交换，然后递归去翻转（invert）交换后的左右子树。等递归结束，整棵树就被镜像（左右翻转）了。

示例与逐步画图（演示树）

假设初始树（按层）：

      1
     / \
    2   3
   / \
  4   5

第一步：调用 invertTree(1)

• root = 1，不为 null
• temp = root.left = 2
• root.left = root.right = 3
• root.right = temp = 2

交换后的暂态（在递归前的树结构）：

      1
     / \
    3   2
       / \
      4   5

注意：4 和 5 仍在 2 的左右，尚未被递归处理（还没翻转它们）。

第二步：递归处理 root.left -> invertTree(3)

• 3 的左右都是 null（或没有子节点）
• swap nulls 后不变，递归结束 结构保持为：

  节点 3（无变化）

第三步：递归处理 root.right -> invertTree(2)

进入 invertTree(2):

• temp = 2.left = 4
• 2.left = 2.right = 5
• 2.right = temp = 4

交换后：

      2
     / \
    5   4

然后递归 invertTree(5)（无子节点）和 invertTree(4)（无子节点），都立即返回。

最终结构

把结果合起来，整棵树变为：

      1
     / \
    3   2
       / \
      5   4

这就是原树的左右镜像。

复杂度

• 时间复杂度：O(n)，每个节点被访问并交换常数次。
• 空间复杂度（递归栈）：O(h)，h 是树高。最坏情况树为链式时 O(n)。

DFS-2

const invertTree = (root) => {
  if (root == null) {
    // 遍历到null节点时，不用翻转，直接返回它本身
    return root;
  }
  invertTree(root.left);
  invertTree(root.right);

  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  return root;
};

输入树：

      1
     / \
    2   3
   / \
  4   5

---

递归展开 + 画图

Step 0 — 调用 invertTree(1)

• root = 1
• 先 invertTree(1.left) → 递归到节点 2

---

Step 1 — 调用 invertTree(2)

• root = 2
• 先 invertTree(2.left) → 递归到节点 4

---

Step 2 — 调用 invertTree(4)

• root = 4
• 先递归左 → null（返回）
• 递归右 → null（返回）
• 然后交换：4.left 和 4.right（null ↔ null，无变化）

返回节点 4。

---

Step 3 — 回到节点 2，继续右子树

• 调用 invertTree(2.right) → 递归到节点 5

节点 5：

• 左递归 null，右递归 null
• 交换 5.left ↔ 5.right → null ↔ null
• 返回 5

---

Step 4 — 回到节点 2（左右子树都处理完了）

• 现在执行交换：2.left ↔ 2.right 即 4 ↔ 5

交换后，局部树变为：

   2
  / \
 5   4

---

Step 5 — 回到根节点 1，处理右子树

• 调用 invertTree(1.right) → 节点 3

节点 3：

• 左递归 null，右递归 null
• 交换 3.left ↔ 3.right（null ↔ null）
• 返回 3

---

Step 6 — 回到根节点 1

• 执行交换：1.left ↔ 1.right 即 2 ↔ 3

最终树变为：

      1
     / \
    3   2
       / \
      5   4

---

调用顺序（递归栈时间线）

invertTree(1)
 ├─ invertTree(2)
 │   ├─ invertTree(4)
 │   │   └─ 交换(4)
 │   ├─ invertTree(5)
 │   │   └─ 交换(5)
 │   └─ 交换(2: 4↔5)
 ├─ invertTree(3)
 │   └─ 交换(3)
 └─ 交换(1: 2↔3)

---

总结对比（前序 vs 后序）

• 前序交换版：进入节点时就交换，再递归子树（交换先做）。
• 后序交换版：先递归处理左右子树，回来时才交换（交换后做）。
• 最终结果：两种方法完全一样，都会得到镜像树。
• 差别：访问顺序不同，在调试和打印过程中能看出差异。

BFS

const invertTree = (root) => {
  if (root == null) {
    return root;
  }
  const queue = [root]; // 维护一个队列，初始推入第一层的root

  while (queue.length) {
    const cur = queue.shift(); // 出列的节点
    [cur.left, cur.right] = [cur.right, cur.left]; // 交换左右子树

    if (cur.left) {
      // 作为下一层节点入列考察
      queue.push(cur.left);
    }
    if (cur.right) {
      queue.push(cur.right);
    }
  }
  return root;
};

逐步演示（每步画图 + 队列变化）

Step 0 — 初始

• 队列（Before）：[1]

      1
     / \
    2   3
   / \
  4   5

---

Step 1 — 处理节点 1

• cur = queue.shift() → cur = 1，队列变 []
• 执行交换：[cur.left, cur.right] = [cur.right, cur.left] 所以 1 的左右子树互换（2 与 3 互换）
• 然后按顺序把 cur.left、cur.right（交换后的）入队

队列（After）：[3, 2]

树（交换后暂态）：

      1
     / \
    3   2
       / \
      4   5

注意：节点 2 的子树（4、5）还没被递归/遍历翻转，仅仅是指针位置被换到右侧。

---

Step 2 — 处理节点 3

• 从队列出列：cur = 3，队列变 [2]
• 3 没有子节点，交换 null 与 null 不改变结构
• 无新节点入队

队列（After）：[2]

树保持不变：

      1
     / \
    3   2
       / \
      4   5

---

Step 3 — 处理节点 2

• cur = 2，队列变 []
• 交换 2 的左右：4 <-> 5
• 把交换后的左右按顺序入队（先 5，再 4）

队列（After）：[5, 4]

树状态：

      1
     / \
    3   2
       / \
      5   4

---

Step 4 — 处理节点 5

• cur = 5，队列变 [4]
• 5 无子节点，交换无效
• 队列仍 [4]

树不变。

---

Step 5 — 处理节点 4

• cur = 4，队列变 []
• 4 无子节点
• 结束（队列空）

最终树（镜像完成）：

      1
     / \
    3   2
       / \
      5   4

101.对称二叉树 easy

• 镜像关系的定义：
  1. 左子树的左节点 = 右子树的右节点
  2. 左子树的右节点 = 右子树的左节点
  3. 节点值也要相等

递归法

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = (root) => {
  const check = (left, right) => {
    if (left == null && right == null) {
      // 两个子树都为null，是对称的
      return true;
    }
    if (left && right) {
      // 两个子树都存在，则需要：root值相同，且他们的子树也满足镜像
      return (
        left.val == right.val && check(left.left, right.right) && check(left.right, right.left)
      );
    }
    return false; // 一个子树存在一个不存在，肯定不对称
  };

  if (root == null) {
    // 如果传入的root就是null，对称
    return true;
  }
  return check(root.left, root.right); // 否则，判断它的左右子树是否满足对称
};

举例一：对称的二叉树

比如下面这棵树：

        1
      /   \
     2     2
    / \   / \
   3  4  4   3

检查过程：

1. check(root.left, root.right)
   • left=2, right=2，值相等
   • 递归比较：check(left.left, right.right) 和 check(left.right, right.left)
2. 比较 left.left=3 和 right.right=3
   • 值相等
   • 两边都没有子节点 → 对称
3. 比较 left.right=4 和 right.left=4
   • 值相等
   • 两边都没有子节点 → 对称

最终返回 true。

---

图解递归过程（对称）

check(2,2)
 ├── check(3,3) → true
 └── check(4,4) → true

每一步就像照镜子，左边的 3 对右边的 3，左边的 4 对右边的 4。

BFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(root == null){
        return true
    }

    let queue = []
    queue.push(root.left,root.right)

    while(queue.length){

        let left = queue.shift()
        let right = queue.shift()

        if((left == null &&right) || (left && right == null)){
            return false
        }
        if(left && right){
            if(left.val !== right.val){
                return false
            }
            queue.push(left.left,right.right)
            queue.push(left.right,right.left)
        }

    }
    return true
};

举例一：对称的树

        1
      /   \
     2     2
    / \   / \
   3  4  4   3

---

Step 1：初始入队

把 root.left=2 和 root.right=2 放进队列：

queue = [2(left), 2(right)]

---

Step 2：出队一对节点 (2,2)

• 都存在，值相等
• 入队顺序：
  • (left.left=3 , right.right=3)
  • (left.right=4 , right.left=4)

queue = [3, 3, 4, 4]

---

Step 3：出队一对节点 (3,3)

• 都存在，值相等
• 入队：它们没有子节点，所以入队 [null, null, null, null]

queue = [4, 4]

---

Step 4：出队一对节点 (4,4)

• 都存在，值相等
• 入队：同样没有子节点

queue = []

队列空了，算法结束 → 返回 true。

543.二叉树的直径 easy

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  let ans = 0;
  function dfs(node) {
    if (node === null) {
      return -1; // 对于叶子来说，链长就是 -1+1=0
    }
    const lLen = dfs(node.left) + 1; // 左子树最大链长+1
    const rLen = dfs(node.right) + 1; // 右子树最大链长+1
    ans = Math.max(ans, lLen + rLen); // 两条链拼成路径
    return Math.max(lLen, rLen); // 当前子树最大链长
  }
  dfs(root);
  return ans;
};

代码里核心思路就是：

• 递归计算每个节点的 左右子树的最大链长（从该节点到叶子节点的最长路径）。
• 直径（两个节点之间的最长路径）一定是 某个节点的左链 + 右链 拼起来的。
• 遍历所有节点，取最大值即可。

例子：

        1
       / \
      2   3
     / \
    4   5

---

执行过程

入口

diameterOfBinaryTree(root=1)
ans = 0
dfs(1)

---

dfs(1)

进入根节点 1

dfs(1):
  lLen = dfs(2) + 1   // 先去算左子树
  rLen = dfs(3) + 1   // 再去算右子树
  ans = max(ans, lLen + rLen)
  return max(lLen, rLen)

---

dfs(2)

进入节点 2

dfs(2):
  lLen = dfs(4) + 1
  rLen = dfs(5) + 1
  ans = max(ans, lLen + rLen)
  return max(lLen, rLen)

---

dfs(4)

进入叶子节点 4

dfs(4):
  lLen = dfs(null) + 1 = -1 + 1 = 0
  rLen = dfs(null) + 1 = -1 + 1 = 0
  ans = max(0, 0+0) = 0
  return max(0,0) = 0

返回 0

---

dfs(5)

进入叶子节点 5

dfs(5):
  lLen = dfs(null) + 1 = 0
  rLen = dfs(null) + 1 = 0
  ans = max(0, 0+0) = 0
  return 0

返回 0

---

回到 dfs(2)

得到左右链长：

lLen = 0 + 1 = 1
rLen = 0 + 1 = 1
ans = max(0, 1+1=2) = 2
return max(1,1) = 1

返回 1

---

dfs(3)

进入节点 3（叶子）

dfs(3):
  lLen = dfs(null)+1 = 0
  rLen = dfs(null)+1 = 0
  ans = max(2, 0+0=0) = 2
  return 0

返回 0

---

回到 dfs(1)

lLen = 1 + 1 = 2   // 来自节点 2
rLen = 0 + 1 = 1   // 来自节点 3
ans = max(2, 2+1=3) = 3
return max(2,1) = 2

返回 2

---

结束

dfs(1) 执行完，最终：

ans = 3

---

最终输出

diameterOfBinaryTree(root) = 3

对应最长路径是： 4 -> 2 -> 1 -> 3 或 5 -> 2 -> 1 -> 3（3 条边）。

直径 = 所有节点的 (左子树深度 + 右子树深度) 的最大值

复杂度分析

• 时间复杂度：O(n)，其中 n 为二叉树的节点个数。
• 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。

102二叉树的层序遍历

两个数组法 优

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (root === null) {
    return [];
  }
  const ans = []; //最后要返回的二维数组，按层保存节点值。
  let cur = [root]; //当前正在处理的整层节点（数组形式）。
  while (cur.length) {
    const nxt = []; //下一层要处理的节点（临时数组）。
    const vals = []; //本次 cur 里所有节点的值（将被 push 到 ans）。
    for (const node of cur) {
      vals.push(node.val);
      if (node.left) nxt.push(node.left);
      if (node.right) nxt.push(node.right);
    }
    cur = nxt;
    ans.push(vals);
  }
  return ans;
};

复杂度分析 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此数组中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。

示例树（ASCII）：

      1
     / \
    2   3
   / \   \
  4   5   6

目标输出：[[1], [2, 3], [4, 5, 6]]

初始化

if (root === null) return [];
const ans = [];
let cur = [root];

此时：

• ans = []
• cur = [1] （包含根节点）

---

第 1 次 while 循环（处理第 1 层）

cur = [1] 创建 nxt = [], vals = []，逐个遍历 cur：

处理节点 1：

• vals.push(1) → vals = [1]
• node.left 存在（2）→ nxt.push(2) → nxt = [2]
• node.right 存在（3）→ nxt.push(3) → nxt = [2,3]

循环结束后：

• ans.push(vals) → ans = [[1]]
• cur = nxt → cur = [2,3]

状态快照（结束第1层）：

cur = [2, 3]
ans = [[1]]

---

第 2 次 while 循环（处理第 2 层）

cur = [2, 3]`
 `nxt = []`, `vals = []

处理节点 2：

• vals.push(2) → vals = [2]
• 2.left = 4 → nxt = [4]
• 2.right = 5 → nxt = [4,5]

处理节点 3：

• vals.push(3) → vals = [2,3]
• 3.left 不存在 → 不 push
• 3.right = 6 → nxt.push(6) → nxt = [4,5,6]

循环结束后：

• ans.push(vals) → ans = [[1], [2,3]]
• cur = nxt → cur = [4,5,6]

状态快照（结束第2层）：

cur = [4, 5, 6]
ans = [[1], [2,3]]

---

第 3 次 while 循环（处理第 3 层）

cur = [4,5,6]`
 `nxt = []`, `vals = []

处理节点 4：vals = [4]，4.left/4.right 都不存在 → nxt 不变 处理节点 5：vals = [4,5]，无子节点 处理节点 6：vals = [4,5,6]，无子节点

循环结束后：

• ans.push(vals) → ans = [[1],[2,3],[4,5,6]]
• cur = nxt → cur = []

现在 cur.length === 0，退出 while。

最终返回 ans = [[1],[2,3],[4,5,6]]，与预期一致。

一个队列法

/**
 * @param {TreeNode} root
 * @return {number[][]}
 * 队列 先进先出（FIFO）
 */

const levelOrder = (root) => {
  if (root === null) {
    return [];
  }
  let result = [];
  const queue = [root]; // 使用数组模拟队列，初始化为根节点

  while (queue.length > 0) {
    // let next = []; // 存储下一层节点
    const vals = [];
    const levelSize = queue.length; // 当前层的节点数量
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift(); // 出队
      vals.push(node.val); // 收集当前层的值

      if (node.left) queue.push(node.left); // 左子节点入队
      if (node.right) queue.push(node.right); // 右子节点入队
    }
    result.push(vals); // 将当前层的结果加入最终结果
  }

  return result;
};

逐步执行（按层 + 每次出队细化）

初始

queue = [1]
result = []

第 1 层（while 第一次）

• levelSize = queue.length = 1
• for 循环 i = 0..0：
  1. node = queue.shift() → node = 1 现在 queue = []（因为 shift 把 1 从队列头移除了）
  2. vals.push(1) → vals = [1]
  3. 入队左右子节点：queue.push(2) → queue = [2]，queue.push(3) → queue = [2,3]
• 本层结束：result.push([1]) → result = [[1]]

快照结束第1层：queue = [2,3], result = [[1]]

---

第 2 层（while 第二次）

• levelSize = queue.length = 2

• for i = 0..1：

  i = 0:

  1. node = queue.shift() → node = 2 ，queue 由 [2,3] 变成 [3]（元素被左移）
  2. vals.push(2) → vals = [2]
  3. 入队 2.left(4) 和 2.right(5) → queue = [3,4,5]

  i = 1:

  1. node = queue.shift() → node = 3 ，queue 由 [3,4,5] 变成 [4,5]
  2. vals.push(3) → vals = [2,3]
  3. 入队 3.right(6) → queue = [4,5,6]

• 本层结束：result.push([2,3]) → result = [[1],[2,3]]

快照结束第2层：queue = [4,5,6], result = [[1],[2,3]]

---

第 3 层（while 第三次）

• levelSize = 3

• for i = 0..2：

  i = 0: shift → node=4, queue→[5,6], vals=[4], 无子节点 i = 1: shift → node=5, queue→[6], vals=[4,5], 无子节点 i = 2: shift → node=6, queue→[], vals=[4,5,6], 无子节点

• 本层结束：result.push([4,5,6]) → result = [[1],[2,3],[4,5,6]]

queue 为空，退出 while，返回 result。

复杂度分析 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此队列中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。

关于 shift() 的性能提醒（重要）

• 在 大多数 JS 引擎 中，Array.prototype.shift() 会把数组前面的元素移除并 将剩下的元素往前重新索引，这是 O(k) 的操作（k = 剩余元素数）。
• BFS 中会对每个节点调用一次 shift()，若树有 n 个节点，总的位移成本可能接近 O(n²)（最坏/平均情况），在大型树或性能敏感场景会变慢。

108.将有序数组转换为二叉搜索树 easy

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * 将有序数组转换为平衡二叉搜索树
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  // 把 nums[start] 到 nums[end-1] 构造成 BST
  function buildTree(startIndex, endIndex) {
    if (startIndex === endIndex) {
      return null; // 区间为空，返回空树
    }
    // 取中间位置作为当前子树的根节点
    const midIndex = Math.floor((startIndex + endIndex) / 2);

    // 递归构造左右子树
    const leftSubtree = buildTree(startIndex, midIndex);
    const rightSubtree = buildTree(midIndex + 1, endIndex);

    return new TreeNode(nums[midIndex], leftSubtree, rightSubtree);
  }

  return buildTree(0, nums.length);
};

复杂度分析 时间复杂度：O(n)，其中 n 是 nums 的长度。每次递归要么返回空节点，要么把 nums 的一个数转成一个节点，所以递归次数是 O(n) 的，所以时间复杂度是 O(n)。需要注意，Python 的第一种写法有切片的复制开销，二叉树的每一层都需要花费 O(n) 的时间，一共有 O(logn) 层，所以时间复杂度是 O(nlogn)；第二种写法避免了切片的复制开销，时间复杂度是 O(n)。 空间复杂度：O(n)。如果不计入返回值和切片的空间，那么空间复杂度为 O(logn)，即递归栈的开销。

例子 A（奇数长度）

nums = [1,2,3,4,5,6,7] （长度 7）

初始调用：dfs(0, 7)

执行过程（带区间和 mid）：

dfs(0,7):
  m = floor((0+7)/2) = 3   -> nums[3] = 4  （根）
  左: dfs(0,3)
  右: dfs(4,7)

dfs(0,3):
  m = floor((0+3)/2) = 1   -> nums[1] = 2
  左: dfs(0,1)
  右: dfs(2,3)

dfs(0,1):
  m = floor((0+1)/2) = 0   -> nums[0] = 1
  左: dfs(0,0) -> null
  右: dfs(1,1) -> null

dfs(2,3):
  m = floor((2+3)/2) = 2   -> nums[2] = 3
  左: dfs(2,2) -> null
  右: dfs(3,3) -> null

dfs(4,7):
  m = floor((4+7)/2) = 5   -> nums[5] = 6
  左: dfs(4,5)
  右: dfs(6,7)

dfs(4,5):
  m = floor((4+5)/2) = 4   -> nums[4] = 5
  左: dfs(4,4) -> null
  右: dfs(5,5) -> null

dfs(6,7):
  m = floor((6+7)/2) = 6   -> nums[6] = 7
  左: dfs(6,6) -> null
  右: dfs(7,7) -> null

最终二叉树（可视化）：

        4
      /   \
     2     6
    / \   / \
   1  3  5  7

每个节点上的数字是 nums[index]；树高度平衡，因为每次都把区间对半分（或接近对半）。

递归调用树（以例 A 为例）

把递归调用也画成树（dfs(left,right)）：

dfs(0,7)
├── dfs(0,3)
│   ├── dfs(0,1)
│   │   ├── dfs(0,0) -> null
│   │   └── dfs(1,1) -> null
│   └── dfs(2,3)
│       ├── dfs(2,2) -> null
│       └── dfs(3,3) -> null
└── dfs(4,7)
    ├── dfs(4,5)
    │   ├── dfs(4,4) -> null
    │   └── dfs(5,5) -> null
    └── dfs(6,7)
        ├── dfs(6,6) -> null
        └── dfs(7,7) -> null

此调用树也反映了构造节点的顺序（左子树先被构建，再构建右子树，最后由构造函数把子节点和根值组装成父节点）。

98.验证二叉搜索树

中序遍历法

var isValidBST = function (root) {
  let pre = -Infinity;
  //pre 用来记录中序遍历中上一个访问的节点值。初始值为 -Infinity，保证第一个节点一定大于它。
  function dfs(node) {
    if (node == null) {
      return true;
    }
    if (!dfs(node.left)) {
      // 左  先递归左子树 dfs(node.left)
      return false;
    }
    if (node.val <= pre) {
      // 中
      return false;
    }
    pre = node.val;
    return dfs(node.right); // 右
  }
  return dfs(root);
};

假设有一棵树：

       5
      / \
     3   7
    / \   \
   2   4   8

核心逻辑就是：

• 中序遍历 BST 得到的序列 严格递增。
• pre 记录上一个访问的节点值。
• 每访问一个节点，检查：

if (node.val <= pre) return false;

• 只要能一直通过这个检查，遍历完整棵树 → 就是 BST。

可以简单理解为：沿着中序遍历顺序，节点值一直比前一个大 → BST。

举例

初始化

let pre = -Infinity;

• pre 用来记录中序遍历中上一个访问的节点值。
• 初始值为 -Infinity，保证第一个节点一定大于它。

---

dfs(root) 开始

根节点 5：

• 先递归左子树 dfs(node.left) → 节点 3

---

访问左子树节点 3

• 递归左子树 dfs(node.left) → 节点 2

---

访问左子树节点 2

• 左子树为空 → dfs(node.left) 返回 true
• 中序“中”步骤：2 <= pre ?
  • 当前 pre = -Infinity，所以 2 > pre
  • 更新 pre = 2
• 右子树为空 → dfs(node.right) 返回 true
• 节点 2 处理完毕，返回 true

此时 pre = 2

---

回到节点 3

• 左子树返回 true
• 检查中序条件：3 <= pre ?
  • 当前 pre = 2，所以 3 > 2
  • 更新 pre = 3
• 递归右子树 → 节点 4

---

访问节点 4

• 左子树为空 → 返回 true
• 中序步骤：4 <= pre ?
  • 当前 pre = 3，所以 4 > 3
  • 更新 pre = 4
• 右子树为空 → 返回 true

此时 pre = 4

• 节点 3 的右子树处理完毕 → 返回 true

---

回到根节点 5

• 左子树返回 true
• 中序步骤：5 <= pre ?
  • 当前 pre = 4，所以 5 > 4
  • 更新 pre = 5
• 递归右子树 → 节点 7

---

访问右子树节点 7

• 左子树为空 → 返回 true
• 中序步骤：7 <= pre ?
  • 当前 pre = 5，所以 7 > 5
  • 更新 pre = 7
• 右子树 → 节点 8

---

访问节点 8

• 左子树为空 → 返回 true
• 中序步骤：8 <= pre ?
  • 当前 pre = 7，所以 8 > 7
  • 更新 pre = 8
• 右子树为空 → 返回 true

---

所有节点访问完毕

• dfs 返回 true
• 说明整棵树是 二叉搜索树（BST）

230.二叉搜索树中第K小的元素

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  let ans = 0;
  function dfs(node) {
    if (node === null || k === 0) {
      return;
    }
    dfs(node.left); // 左
    if (--k === 0) {
      ans = node.val; // 根
    }
    dfs(node.right); // 右
  }
  dfs(root);
  return ans;
};

复杂度分析 时间复杂度：O(n)，其中 n 是二叉树的大小（节点个数）。 空间复杂度：O(h)，其中 h 是树高，递归需要 O(h) 的栈空间。最坏情况下树是一条链，h=n，空间复杂度为 O(n)。

示例

我们用一个简单的 BST 举例：

        5
       / \
      3   6
     / \
    2   4
   /
  1

假设 k = 3，也就是要找 第 3 小的元素。 BST 的 中序遍历结果是升序的：

1, 2, 3, 4, 5, 6

所以第 3 小的数是 3。

---

代码逻辑

代码里做的其实就是 中序遍历 (左 → 根 → 右)，并用 k 计数。

• 每访问一个节点，k 就减 1
• 当 k === 0 时，当前节点值就是答案

---

执行过程图解

初始

k = 3, ans = 0
从 root = 5 开始 dfs

---

进入左子树 (节点 5 → 3 → 2 → 1)

dfs(5) → dfs(3) → dfs(2) → dfs(1)

到达最左节点 1。

---

处理节点 1

• dfs(1.left) → null 返回
• --k = 2 （原本是 3，减 1 变 2）
• ans 还没赋值，因为 k ≠ 0
• dfs(1.right) → null 返回

k = 2, ans = 0

---

回到节点 2

• 左边走完了，开始处理 2
• --k = 1
• ans 还没赋值
• dfs(2.right) → null

k = 1, ans = 0

---

回到节点 3

• 处理 3
• --k = 0 ✅ 找到了
• ans = 3

k = 0, ans = 3

此时答案锁定为 3。

---

后续遍历提前终止

因为 k === 0，dfs 里开头有 if (node === null || k === 0) return; 所以后续节点（4,5,6）就不用再遍历了，直接结束。

---

最终结果

return ans = 3

---

总结

1. 中序遍历 BST → 得到递增序列。
2. 用 k 控制，访问一个节点 k--。
3. 当 k === 0 时，当前节点值就是第 k 小的数。

199.二叉树的右视图

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
  //二叉树右视图 只需要把每一层最后一个节点存储到res数组
  let res = [],
    queue = [];
  queue.push(root);
  while (queue.length && root !== null) {
    // 记录当前层级节点个数
    let length = queue.length;
    while (length--) {
      let node = queue.shift();
      //length长度为0的时候表明到了层级最后一个节点
      if (!length) {
        res.push(node.val);
      }
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }
  }
  return res;
};

示例二叉树

我们用下面的二叉树举例：

        1
       / \
      2   3
       \   \
        5   4

右视图的结果应该是 [1, 3, 4]。

---

执行过程

初始化：

• queue = [1]
• res = []

---

第一层：

• length = 1（只有一个节点）
• 出队 1，此时 length=0（这一层最后一个节点），加入结果 → res = [1]
• 入队 2, 3
• queue = [2, 3]

---

第二层：

• length = 2（有两个节点：2, 3）

1. 出队 2，length=1（不是最后一个，忽略） 入队 2.right = 5 → queue = [3, 5]
2. 出队 3，length=0（最后一个节点，记录） → res = [1, 3] 入队 3.right = 4 → queue = [5, 4]

---

第三层：

• length = 2（有两个节点：5, 4）

1. 出队 5，length=1（不是最后一个，忽略） 5没有子节点，所以不入队 → queue = [4]
2. 出队 4，length=0（最后一个节点，记录） → res = [1, 3, 4]4没有子节点 → queue = []

---

结束：

• 队列空了，遍历完毕
• 最终结果：[1, 3, 4]

---

过程图解

层序遍历队列变化过程：
queue = [1]         → res = [1]
queue = [2, 3]      → res = [1, 3]
queue = [5, 4]      → res = [1, 3, 4]
queue = []          → 结束

时间复杂度

代码的核心是 层序遍历（BFS）：

• 每个节点 只会入队一次、出队一次；
• 出队时会检查 node.left 和 node.right，这是 O(1) 操作；
• 其他操作（记录最后一个节点到 res）也是 O(1)。

所以，总体时间复杂度：

O(n)

其中 nnn 是二叉树的节点数。

---

空间复杂度

空间主要来自 队列 queue 和 结果数组 res：

1. 队列 queue：
   • 最坏情况下，某一层可能有最多 n2\frac{n}{2}2n 个节点（例如满二叉树的最后一层）。
   • 所以队列最大占用空间是 O(n)。
2. 结果数组 res：
   • 存储的是每一层最后一个节点值。
   • 树的高度为 h，则 res 长度最多是 h。
   • 对于 n 个节点的树，高度 h 最坏情况是 n（链表树），所以 res 占用 O(h)，最坏 O(n)。

综合下来：

O(n)

114.二叉树展开为链表

头插法

采用头插法构建链表，也就是从节点 6 开始，在 6 的前面插入 5，在 5 的前面插入 4，依此类推。

为此，要按照 6→5→4→3→2→1 的顺序访问节点。如何遍历这棵树，才能实现这个顺序？

按照右子树 - 左子树 - 根的顺序 DFS 这棵树。

DFS 的同时，记录当前链表的头节点为 head。一开始 head 是空节点。

具体来说：

如果当前节点为空，返回。 递归右子树。 递归左子树。 把 root.left 置为空。 头插法，把 root 插在 head 的前面，也就是 root.right=head。 现在 root 是链表的头节点，把 head 更新为 root。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  let head = null;
  function dfs(node) {
    if (node === null) {
      return;
    }
    dfs(node.right);
    dfs(node.left);
    node.left = null;
    node.right = head; // 头插法，相当于链表的 node.next = head
    head = node; // 现在链表头节点是 node
  }
  dfs(root);
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点个数。
• 空间复杂度：O(n)。递归需要 O(n) 的栈空间。

逐步图解（用经典示例树来说明）

我们用这个常见的例子来说明执行过程：

      1
     / \
    2   5
   / \   \
  3   4   6

算法核心是：反前序遍历（右 -> 左 -> 根） + 头插法。 伪代码关键三行：

node.left = null;
node.right = head; // 把已构造的链表接到当前节点的右指针
head = node;       // 更新链表头

初始：head = null。

---

总体执行顺序（处理节点的顺序）

由于函数先 dfs(node.right) 再 dfs(node.left)，然后处理 node，被“处理”（执行三行修改）的节点顺序是：

6 -> 5 -> 4 -> 3 -> 2 -> 1

每次处理时，把当前节点“头插”到已经由 head 指向的链表前面，最终得到的右指针链是前序遍历顺序：1 -> 2 -> 3 -> 4 -> 5 -> 6。

---

逐步图示（每步画出 head 与链状结构）

步骤 0（初始）

树（结构不变）:             head = null
      1
     / \
    2   5
   / \   \
  3   4   6

---

步骤 1：到达并处理节点 6

调用栈到 dfs(6)，左右子都为空，开始处理 6：

执行：

6.left = null;
6.right = head; // head 是 null
head = 6;

结果：

head -> 6 -> null

树上 5.right 仍指向 6（还没改 5 的时候）

---

步骤 2：返回处理节点 5

现在 head = 6。处理 5（5.left 原本为 null，5.right 原本指向 6）：

执行：

5.left = null;      // 没变化
5.right = head;     // 指向 6（和原来相同）
head = 5;

结果链：

head -> 5 -> 6 -> null

树的剩余结构（概念上）：

      1
     / \
    2   5
   / \    \
  3   4    6
但此时 head 链为 5->6

---

步骤 3：回到左子树，处理节点 4

head = 5。处理 4（原来 4.right = null）：

执行：

4.left = null;
4.right = head;  // 指向 5
head = 4;

结果链：

head -> 4 -> 5 -> 6 -> null

注意：2.right 原本指向 4，但现在 4.right 已被改为 5，所以 2 的右子仍是 4（但 4 的右子变成 5）。

步骤 4：处理节点 3

head = 4。处理 3（叶子）：

执行：

3.left = null;
3.right = head;  // 指向 4
head = 3;

结果链：

head -> 3 -> 4 -> 5 -> 6 -> null

---

步骤 5：处理节点 2

head = 3。处理 2（原来 2.left=3, 2.right=4）：

执行：

2.left = null;   // 删掉原来的左链 3
2.right = head;  // 指向 3（之前 head 指向 3）
head = 2;

结果链：

head -> 2 -> 3 -> 4 -> 5 -> 6 -> null

（2 原来指向 4，现在改为直接指向 3，3->4->5->6 保持不变）

---

步骤 6：处理根节点 1（结束）

head = 2。处理 1：

执行：

1.left = null;
1.right = head; // 指向 2
head = 1;

最终链：

head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

此时整棵树被“拉平”为单链（所有 left 都 = null，right 链即是前序遍历顺序）。

---

为什么能得到前序（根-左-右）顺序？

• 我们按 右、左、根 的顺序递归，然后在回溯处把当前节点头插到 head 前面。
• 每次处理某个节点时，head 已经是“右子树 + 之前处理过的部分”组成的链表，把当前节点放到 head 前面，保证根放在它的左子树和右子树之前。按此递归展开，最终顺序为前序（根，左子树，右子树）。

105.从前序与中序遍历序列构造二叉树

基础概念

我们拿一个小点的树：

        A
       / \
      B   C
     / \
    D   E

---

前序遍历（Preorder）

规则：根 → 左子树 → 右子树

执行过程：

1. 先访问根 A
2. 再访问左子树（根是 B）
   • 访问 B
   • 进入 B 的左子树 → D
   • 进入 B 的右子树 → E
3. 最后访问右子树（C）

遍历顺序：

A → B → D → E → C

所以前序遍历结果是：

[A, B, D, E, C]

---

中序遍历（Inorder）

规则：左子树 → 根 → 右子树

执行过程：

1. 先进入 A 的左子树（根是 B）
   • 再进入 B 的左子树 → D
   • 回到 B
   • 再进入 B 的右子树 → E
2. 回到根 A
3. 进入 A 的右子树 → C

遍历顺序：

D → B → E → A → C

所以中序遍历结果是：

[D, B, E, A, C]

var buildTree = function (preorder, inorder) {
  const n = preorder.length;
  if (n === 0) {
    // 没有节点
    return null;
  }

  const rootVal = preorder[0]; // 前序遍历的第一个一定是根节点
  const rootIndexInorder = inorder.indexOf(rootVal); // 根节点在中序遍历中的位置
  const leftSubtreeSize = rootIndexInorder; // 左子树节点数量

  // 左子树的前序遍历
  const preorderLeft = preorder.slice(1, 1 + leftSubtreeSize);
  // 右子树的前序遍历
  const preorderRight = preorder.slice(1 + leftSubtreeSize);

  // 左子树的中序遍历
  const inorderLeft = inorder.slice(0, rootIndexInorder);
  // 右子树的中序遍历
  const inorderRight = inorder.slice(rootIndexInorder + 1, n);

  // 递归构造左右子树
  const leftSubtree = buildTree(preorderLeft, inorderLeft);
  const rightSubtree = buildTree(preorderRight, inorderRight);

  return new TreeNode(rootVal, leftSubtree, rightSubtree);
};

递归调用树（按调用层次）

buildTree([3,9,20,15,7], [9,3,15,20,7])
├─ left:  buildTree([9], [9])  -> returns TreeNode(9)
└─ right: buildTree([20,15,7], [15,20,7])
    ├─ left:  buildTree([15], [15]) -> TreeNode(15)
    └─ right: buildTree([7], [7])   -> TreeNode(7)

437.路径总和3 有点不懂

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
const pathSum = function (root, targetSum) {
  let ans = 0;
  const cnt = new Map();
  cnt.set(0, 1); // 把 s[0] = 0 统计进来
  function dfs(node, s) {
    if (node === null) {
      return;
    }

    s += node.val;
    // 把 node 当作路径的终点，统计有多少个起点
    ans += cnt.get(s - targetSum) ?? 0;

    cnt.set(s, (cnt.get(s) ?? 0) + 1); // cnt[s]++
    dfs(node.left, s);
    dfs(node.right, s);
    cnt.set(s, cnt.get(s) - 1); // 恢复现场（撤销 cnt[s]++）
  }
  dfs(root, 0);
  return ans;
};

树（targetSum = 8）：

       10
      /  \
     5   -3
    / \    \
   3   2    11
  / \   \
 3  -2   1

---

访问顺序（DFS，先序）

10 → 5 → 3 → 3 → -2 → 2 → 1 → -3 → 11

下面每一帧都写清楚：当前节点、s（前缀和）、查询 s - target、cnt 的变化、ans 是否增加，以及如果增加，说明哪条路径被找到。

---

初始

• cnt = {0:1}（代表空路径和为 0 出现过 1 次，方便从根开始计算）
• ans = 0
• s 初始为 0

---

Step 1 — 到根节点 10

• 到达 10：s = 0 + 10 = 10
• 查询 s - target = 10 - 8 = 2 → cnt[2] = 0，没找到新路径
• 把 s=10 加入 cnt：cnt = {0:1, 10:1}
• ans = 0

（继续往左）

---

Step 2 — 到 5（根的左子）

• 到达 5：s = 10 + 5 = 15
• 查询 s - target = 15 - 8 = 7 → cnt[7] = 0
• 加入 s=15：cnt = {0:1, 10:1, 15:1}
• ans = 0

---

Step 3 — 到 3（5 的左子）

• 到达 3：s = 15 + 3 = 18
• 查询 s - target = 18 - 8 = 10 → cnt[10] = 1，找到 1 条路径
• 为什么是路径 5 → 3？
  • cnt[10] 表示之前在某个位置出现过前缀和 10（正好是根节点 10 的位置）。
  • 当前 s=18，减去之前的 10，中间那段的和 18 - 10 = 8。
  • 那段中间的节点就是从 根之后的节点（也就是节点 5）开始，到当前节点 3 为止：5 → 3。
• 更新 ans = 0 + 1 = 1
• 再把 s=18 加入 cnt：cnt = {0:1, 10:1, 15:1, 18:1}

找到的路径（突出显示）：

       10
      /  \
    [5]   -3
    / \
  [3]  2
  ...

（标为 [ ] 的是这次被识别的路径节点：5 → 3）

---

Step 4 — 到 3 的左子 3（叶）

• 到达这个 3：s = 18 + 3 = 21
• 查询 21 - 8 = 13 → cnt[13] = 0，没找到
• 加入 s=21：cnt = {0:1,10:1,15:1,18:1,21:1}
• 这个节点是叶，回溯时撤销 21：cnt 恢复到 {0:1,10:1,15:1,18:1}

---

Step 5 — 回到 3 然后到 -2（3 的右子）

• 到达 -2：这里 s 从父节点的 18 继续：s = 18 + (-2) = 16
• 查询 16 - 8 = 8 → cnt[8] = 0
• 加入 s=16，遍历后回溯撤销 16（所以不影响其它分支）
• cnt 回到 {0:1,10:1,15:1,18:1}（随后回溯离开父 3，撤销 18）

（离开 3 的子树，回到节点 5）

---

Step 6 — 回到 5，去 5 的右子 2

• 到达 2：s 为父（5）的 15，再加 2 → s = 15 + 2 = 17
• 查询 17 - 8 = 9 → cnt[9] = 0
• 加入 s=17：cnt = {0:1,10:1,15:1,17:1}

---

Step 7 — 到 1（2 的右子）

• 到达 1：s = 17 + 1 = 18
• 查询 18 - 8 = 10 → cnt[10] = 1，又找到 1 条路径
• 这次找到的是 5 → 2 → 1：
  • s(current)=18，s - target = 10，而 cnt[10] 对应的是根（前缀和 10）。
  • 则从根之后到当前的路径 (即从节点 5 开始) 的和是 18 - 10 = 8 → 5 + 2 + 1 = 8。
• 更新 ans = 1 + 1 = 2
• 把 s=18 加入/更新（注意之前 18 在别的分支出现过但已被撤回，所以这里成为当前分支的 18）：cnt = {0:1,10:1,15:1,17:1,18:1}
• 遍历完 1 后回溯撤销 18 和 17（回到只剩 {0:1,10:1}）

第二条被识别的路径：

5 → 2 → 1

---

Step 8 — 回到根，去根的右子 -3

• 回到根（撤销 15），当前 cnt 恢复为 {0:1,10:1}
• 到达 -3：s = 10 + (-3) = 7
• 查询 7 - 8 = -1 → cnt[-1] = 0
• 把 s=7 加入：cnt = {0:1,10:1,7:1}

---

Step 9 — 到 11（-3 的右子）

• 到达 11：s = 7 + 11 = 18
• 查询 18 - 8 = 10 → cnt[10] = 1，再找到 1 条路径
• 这次找到的是 -3 → 11：
  • s(current)=18，减去之前的 10（根的前缀）后中间段和为 8。
  • 这里 “中间段” 对应的是从根之后（也就是从 -3 开始）到当前节点：-3 + 11 = 8。
• 更新 ans = 2 + 1 = 3
• 回溯撤销 18、7，最后 cnt 恢复为 {0:1}

---

最终结论

• ans = 3（总共找到了 3 条符合条件的路径）
• 具体路径为：
  1. 5 → 3
  2. 5 → 2 → 1
  3. -3 → 11

只需要输出路径数目，不需要输出具体路径是什么

恢复现场是为了让左右子支不互相干扰，因为题目要求了只能从父节点到子节点

236.二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (root === null || root === p || root === q) {
    return root; // 找到 p 或 q 就不往下递归了
  }
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) {
    // 左右都找到
    return root; // 当前节点是最近公共祖先
  }
  // 如果只有左子树找到，就返回左子树的返回值
  // 如果只有右子树找到，就返回右子树的返回值
  // 如果左右子树都没有找到，就返回 null（注意此时 right = null）
  return left ?? right;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为二叉树的节点个数。
• 空间复杂度：O(n)。最坏情况下，二叉树是一条链，因此递归需要 O(n) 的栈空间。

例子1

我们用下面这棵二叉树：

          3
        /   \
       5     1
      / \   / \
     6   2 0   8
        / \
       7   4

• p = 5
• q = 1

问题：p=5 和 q=1 的最近公共祖先是谁？

---

代码执行过程

第一次调用

lowestCommonAncestor(root=3, p=5, q=1)

• root 既不是 null，也不是 p 或 q。
• 递归左子树 → lowestCommonAncestor(5, 5, 1)
• 递归右子树 → lowestCommonAncestor(1, 5, 1)

---

递归左子树

lowestCommonAncestor(root=5, p=5, q=1)

• root 就是 p → 直接返回 5。

所以 left = 5。

---

递归右子树

lowestCommonAncestor(root=1, p=5, q=1)

• root 就是 q → 直接返回 1。

所以 right = 1。

---

回到 root=3

• 此时 left=5，right=1，两个子树都找到了目标节点。
• 根据代码：

if (left && right) return root;

→ 返回 3。

所以最近公共祖先是 3。

例子2

（p = 6，q = 4）

先把树再贴一下（方便看）：

          3
        /   \
       5     1
      / \   / \
     6   2 0   8
        / \
       7   4


调用从根 3 开始，下面是逐层调用与返回的清单（缩进表示递归深度）：

1) lowestCommonAncestor(3, 6, 4)
  2) lowestCommonAncestor(5, 6, 4)    // 进入左子树
    3) lowestCommonAncestor(6, 6, 4)
       - root === p (6)，直接 return 6
    <- 返回到 node 5，left = 6

    4) lowestCommonAncestor(2, 6, 4)  // 5 的右子树
      4.1) lowestCommonAncestor(7, 6, 4)
         - 7 不是 p/q，左右都是 null -> return null
      <- 返回到 node 2，left = null

      4.2) lowestCommonAncestor(4, 6, 4)
         - root === q (4)，直接 return 4
      <- 返回到 node 2，right = 4

      // 在 node 2： left = null, right = 4 -> 返回 4（left && right 不成立）
      <- lowestCommonAncestor(2,6,4) 返回 4

    // 在 node 5： left = 6, right = 4 -> left && right 为真 -> 返回 node 5 作为 LCA
    <- lowestCommonAncestor(5,6,4) 返回 5

  <- 回到根 3，left = 5

  5) lowestCommonAncestor(1, 6, 4)    // 进入右子树
    5.1) lowestCommonAncestor(0, 6, 4) -> 返回 null
    5.2) lowestCommonAncestor(8, 6, 4) -> 返回 null
    // node 1：left = null, right = null -> 返回 null
  <- lowestCommonAncestor(1,6,4) 返回 null

// 根 3：left = 5, right = null -> 返回 left（即 5）
<- lowestCommonAncestor(3,6,4) 返回 5


最终结果：最近公共祖先是节点 5。

整体逻辑直观版

1. 自底向上搜索： 每个子树调用 lowestCommonAncestor 会告诉父节点：“我这边找到了什么”。
   • 如果没找到 → null
   • 如果找到一个目标 → 返回那个节点（就相当于把“证据”交给父节点）
   • 如果左右子树都交了“证据” → 父节点就是两者最近相遇点 → 返回父节点作为最近公共祖先
2. 一层层往上汇报： 就像你说的，“子树有对应值，就把它往上传”。 父节点拿到左右返回值后，再决定返回自己还是继续传某个子树的结果。

---

(p=6, q=4)

• 6 的子树返回 6
• 4 的子树返回 4
• 到了它们的父节点 5：左右分别汇报 6 和 4 → 父节点就知道自己是最近公共祖先 → 返回 5
• 再往上传：根 3 收到左子树的返回 5，右子树没结果 → 就继续传 5
• 最后起点（根节点）拿到的结果就是 5

---

内在机制

所以可以总结为：

• 每个子树都尽力往上传“找到的证据”
• 第一次能把两个目标的“证据”汇合的节点，就是最近公共祖先

双指针

283.移动零easy

方法1： 把nums当作栈

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let stackSize = 0;
  for (const x of nums) {
    if (x !== 0) {
      nums[stackSize++] = x; // 把 x 入栈
    }
  }
  nums.fill(0, stackSize);
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 的长度。
• 空间复杂度：O(1)

在最坏情况下（nums 全为 0），需要遍历 nums 两次。

第一层遍历

for (const x of nums) { ... }

这里是 第一次完整遍历数组。

• 如果数组长度是 n，就一定会执行 n 次循环。
• 里面的判断 if (x !== 0) 在“最坏情况”即 全为 0 的时候，始终不会进入 if 分支，只是不断比较。
• 所以这一步花费 O(n)。

---

第二层遍历

nums.fill(0, stackSize);

Array.prototype.fill(value, start) 会把数组从 start 下标开始，填充到末尾。

• 当 nums 全为 0 的时候，stackSize = 0，那么 fill(0, 0) 就会把 整个数组都填充一遍。
• 这相当于又遍历了一次数组（n 次赋值操作）。
• 所以这一步也是 O(n)。

方法2：双指针交换元素

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let i0 = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      [nums[i], nums[i0]] = [nums[i0], nums[i]];
      i0++;
    }
  }
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 的长度。
• 空间复杂度：O(1)。

11.盛最多水的容器

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let ans = 0,
    left = 0,
    right = height.length - 1;
  //ans用来存最大值，area用来计算当前面积
  while (left < right) {
    const area = (right - left) * Math.min(height[left], height[right]);
    ans = Math.max(ans, area);
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return ans;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为 height 的长度。
• 空间复杂度：O(1)，仅用到若干额外变量

木桶效应，装水量受限于最短的板

为什么要移动「短板」？

这是算法的灵魂。

假设当前左边高度小：height[left] < height[right]。

• 如果我移动 右指针： 宽度减小了，但高度依然 ≤ height[left]。 因为短板没变（依然是左边的那根），所以新的面积一定 ≤ 旧面积。 → 没有任何提升的可能性。
• 如果我移动 左指针： 虽然宽度变小，但「短板」可能会变高（如果遇到更高的柱子）。 那么 min(height[left], height[right]) 可能增加，新的面积可能变大。 → 仍然有提升空间。

所以： 每次都应该丢掉「更短」的那根柱子，去赌另一边能不能找到更高的短板。

这就是“双指针法”的内在逻辑。

15.三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let ans = [];
  const len = nums.length;
  if (nums == null || len < 3) return ans;
  nums.sort((a, b) => a - b); // 排序 升序
  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
    if (i > 0 && nums[i] == nums[i - 1]) continue; // 外层去重
    let L = i + 1;
    let R = len - 1;
    while (L < R) {
      const sum = nums[i] + nums[L] + nums[R];
      if (sum == 0) {
        ans.push([nums[i], nums[L], nums[R]]);
        while (L < R && nums[L] == nums[L + 1]) L++; // 去重
        while (L < R && nums[R] == nums[R - 1]) R--; // 去重
        L++;
        R--;
      } else if (sum < 0) L++;
      else if (sum > 0) R--;
    }
  }
  return ans;
};

去重的必要性和逻辑

（1）外层循环去重：

if (i > 0 && nums[i] == nums[i-1]) continue;

含义：如果当前固定的 nums[i] 和前一个数相等，那我们就跳过。

原因： 假如数组是 [-1, -1, 0, 1, 2]，

• 当 i=1 时（第一个 -1），我们会找到 [-1, 0, 1]。

• 当 i=2 时（第二个 -1），如果不跳过，固定它再跑双指针，还是会得到 [-1, 0, 1]，就重复了。

  逻辑本质： 排序之后，相同的数会挨在一起。 如果你用相同的数去固定一次，再用相同的数固定第二次，找到的组合必然是重复的。 所以外层必须去重。

---

（2）内层左指针去重：

while (L < R && nums[L] == nums[L+1]) L++;

含义：当找到一组解 (nums[i], nums[L], nums[R]) 之后，如果下一个 nums[L+1] 跟 nums[L] 一样，那说明换到它得到的解也一样。

举例： 数组片段 [-1, -1, 2]

• 第一次 L=1, R=5，得到 [-1, -1, 2]

• 如果我们不去重，L=2, R=5 又得到同样的 [-1, -1, 2]。

  逻辑本质： 防止相同的左值重复导致相同三元组。

---

（3）内层右指针去重：

while (L < R && nums[R] == nums[R-1]) R--;

道理和左指针一样。 如果右边有连续的相同数字，固定了一个之后，紧挨着的那个一定也会得到重复解。

---

总结去重逻辑：

• 外层去重：防止固定的数 nums[i] 重复。
• 内层去重：防止在找到一个解之后，左右指针继续停留在相同数上导致重复解。

核心思想：排序后，相同的数是连在一起的 → 如果不跳过，就会产生重复解。

例子

nums = [-2, -1, -1, 0, 1, 2]

先排序：

[-2, -1, -1, 0, 1, 2]

---

外层循环 i

i = 0 → nums[i] = -2

• L = 1 → nums[L] = -1
• R = 5 → nums[R] = 2

计算：-2 + (-1) + 2 = -1 → sum < 0 → L++

i=0(-2) | L=2(-1) | R=5(2)

sum = -2 + (-1) + 2 = -1 → sum < 0 → L++

i=0(-2) | L=3(0) | R=5(2)

sum = -2 + 0 + 2 = 0 ✅ 找到一个解：[-2, 0, 2]

然后去重 & 移动：

• L=4, R=4 → while 循环结束

---

i = 1 → nums[i] = -1

• L = 2 → nums[L] = -1
• R = 5 → nums[R] = 2

sum = -1 + (-1) + 2 = 0 ✅ 解：[-1, -1, 2]

去重后：

• L = 3, R = 4 sum = -1 + 0 + 1 = 0 ✅ 解：[-1, 0, 1]

---

i = 2 → nums[i] = -1

⚠️ 这时发现和 i=1 一样，所以 跳过（外层去重）。

---

i = 3 → nums[i] = 0

• L = 4 (1), R = 5 (2) sum = 0 + 1 + 2 = 3 > 0 → R-- 最后 L ≥ R，结束。

---

最终结果

[[-2, 0, 2], [-1, -1, 2], [-1, 0, 1]]

滑动窗口

滑动窗口（Sliding Window）是什么？

滑动窗口是一种处理「连续子串／子数组」问题的通用技巧。核心思路是用两个指针 start（窗口左端）和 end（窗口右端）维护一个窗口 [start, end]，动态地扩张或收缩这个窗口，使窗口始终满足某个不变条件（例如「窗口内字符都不重复」或「窗口内元素和 ≤ k」）。这样可以把暴力枚举 O(n²) 的问题降到 O(n)：每个元素最多被加入和移出窗口一次。

3.无重复字符的最长子串

注意子串和子序列的区别，字符连续才是子字符串

哈希表（整形数组）

/**
 * @param {string} s
 * @return {number}
 */
/**
 * 返回字符串中最长的不含重复字符的子串长度
 * @param {string} str
 * @return {number}
 */
var lengthOfLongestSubstring = function (str) {
  let maxLen = 0; // 记录遇到的最长长度
  let start = 0; // 窗口左端索引（inclusive）
  const charCount = new Map(); // 窗口中每个字符的出现次数

  for (let end = 0; end < str.length; end++) {
    const ch = str[end];
    // 将当前字符加入窗口计数
    charCount.set(ch, (charCount.get(ch) ?? 0) + 1);

    // 如果因加入 ch 导致出现重复（ch 的计数 > 1），就不断右移 start，直到窗口中没有重复 ch
    //一定要把重复了的那个字符去掉
    while (charCount.get(ch) > 1) {
      const leftChar = str[start];
      charCount.set(leftChar, charCount.get(leftChar) - 1);
      start++; // 缩小窗口左端
    }

    // 更新答案：当前窗口长度是 end - start + 1
    maxLen = Math.max(maxLen, end - start + 1);
  }

  return maxLen;
};

用例：str = "abcabcbb" 的逐步执行（画图 + 说明）

字符串索引（方便参照）：

index: 0 1 2 3 4 5 6 7
chars: a b c a b c b b

下面给出每一步 end 移动时的关键状态（先把字符加入窗口，然后如果重复就缩左端）：

step(end)	加入的字符 ch	charCount（加入后）	while（缩左端步骤）	start（最终）	当前窗口 [start,end]	窗口长度	maxLen
0	'a'		无	0	[0,0] = "a"	1	1
1	'b'		无	0	[0,1] = "ab"	2	2
2	'c'		无	0	[0,2] = "abc"	3	3
3	'a'		移除 s[0]='a' → {a:1,b:1,c:1}，start = 1	1	[1,3] = "bca"	3	3
4	'b'		移除 s[1]='b' → {a:1,b:1,c:1}，start = 2	2	[2,4] = "cab"	3	3
5	'c'		移除 s[2]='c' → {a:1,b:1,c:1}，start = 3	3	[3,5] = "abc"	3	3
6	'b'		移除 s[3]='a' → {a:0,b:2,c:1}，start=4; 仍 >1，移除 s[4]='b'→{a:0,b:1,c:1}，start=5	5	[5,6] = "cb"	2	3
7	'b'		移除 s[5]='c' → {a:0,b:2,c:0}，start=6; 仍 >1，移除 s[6]='b'→{a:0,b:1,c:0}，start=7	7	[7,7] = "b"	1	3

最终 maxLen = 3，最长不重复子串为 "abc"（有多个位置）。

---

代码执行流程要点（逐步理解）

1. 主循环（for end）把窗口往右扩：每次把 str[end] 的计数加 1，表示它进入窗口。
2. 检测重复并收缩窗口（while）：只有刚加入的 ch 可能把计数变成 2，因此用 while (charCount.get(ch) > 1) 不断把 start 向右移，每移动一步就把被移出的字符计数减 1，直到 ch 的计数恢复为 1（窗口中没有重复）。
3. 在每一步维护不变式：循环结束时，窗口 [start,end] 中的所有字符都是唯一的（每个字符计数 ≤ 1）。因此可以安全地用 end - start + 1 更新 maxLen。
4. 复杂度：时间 O(n) —— 每个字符最多被 end 加入一次、被 start 移出一次，所以操作数线性。空间 O(min(n, Σ)) —— 取决于字符集大小（Map 的存储）。

438.找到字符串中所有字母异位词

题目要求：

找到 text 中所有长度等于 pattern，并且是 字母异位词 的子串。

字母异位词的核心条件：

• 子串和 pattern 含有 完全相同的字母，出现次数也一样。
• 顺序可以不同

定长滑动窗口

/**
 * @param {string} text    - 主串
 * @param {string} pattern - 模式串
 * @return {number[]}      - 所有字母异位词的起始下标
 */
var findAnagrams = function (text, pattern) {
  const result = [];
  const charCountMap = new Map(); // 存 pattern 字母频率

  // 1️⃣ 统计 pattern 的字母出现次数
  for (const char of pattern) {
    charCountMap.set(char, (charCountMap.get(char) || 0) + 1);
  }

  // 2️⃣ 初始化窗口，减去窗口内的字母
  for (let i = 0; i < pattern.length; i++) {
    const char = text[i];
    if (charCountMap.has(char)) {
      charCountMap.set(char, charCountMap.get(char) - 1);
    }
  }

  // 3️⃣ 滑动窗口
  for (let start = 0, end = pattern.length; end <= text.length; start++, end++) {
    // 检查是否所有字母次数归零
    if ([...charCountMap.values()].every((count) => count === 0)) {
      result.push(start);
    }

    // 左边字母移出窗口
    const leftChar = text[start];
    if (charCountMap.has(leftChar)) {
      charCountMap.set(leftChar, charCountMap.get(leftChar) + 1);
    }

    // 右边字母进入窗口
    const rightChar = text[end];
    if (charCountMap.has(rightChar)) {
      charCountMap.set(rightChar, charCountMap.get(rightChar) - 1);
    }
  }

  return result;
};

核心思路：滑动窗口 + 计数

1. 滑动窗口
   • 窗口长度固定为 pattern.length，从 text 的开头滑到末尾。
   • 每次窗口移动，左边一个字母出去，右边一个字母进来。
2. 计数 Map
   • charCountMap 用来记录每个字母还差多少才能凑成异位词：
     • 初始化：pattern 每个字母 +1
     • 窗口进入时：字母计数 -1
     • 窗口移出时：字母计数 +1
3. 判断条件
   • 当 Map 中所有值都是 0 → 窗口中的字母完全匹配 pattern → 找到异位词。

举例说明

假设：

text = "cbaebabacd"
pattern = "abc"

目标：找到所有与 "abc" 是 字母异位词 的子串。

---

Step 1️⃣ 初始化 Map

pattern = "abc"
charCountMap = { a:1, b:1, c:1 }

---

Step 2️⃣ 初始化窗口（前 3 个字符 "cba"）

• 遍历 text[0..2]，减去窗口字母次数：
  • 'c' →
  • 'b' →
  • 'a' →
• 检查 Map 值是否全是 0 ✅
  • 是 → 第一个异位词下标 0，result = [0]

---

Step 3️⃣ 滑动窗口

移动窗口 1

• 左边移出 'c' →
• 右边加入 'e' → 'e' 不在 Map → 不修改
• Map.values() = [0,0,1] ❌ → 不是异位词

移动窗口 2

• 左边移出 'b' →
• 右边加入 'b' →
• Map.values() = [0,0,1] ❌

移动窗口 3

• 左边移出 'a' →
• 右边加入 'a' → { a:0, b:0, c:1 } ❌

移动窗口 4

• 左边移出 'e' → 'e' 不在 Map → 不修改
• 右边加入 'b' → { a:0, b:-1, c:1 } ❌

移动窗口 5

• 左边移出 'b' → { a:0, b:0, c:1 } ❌
• 右边加入 'a' → { a:-1, b:0, c:1 } ❌

移动窗口 6

• 左边移出 'a' →
• 右边加入 'c' → { a:0, b:0, c:0 } ✅
• 异位词下标 = 6 → result = [0,6]

---

Step 4️⃣ 结束

• 滑动到文本结尾 → result = [0,6]

子串

560.和为K的子数组

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const subarraySum = (nums, targetSum) => {
  const prefixSumCountMap = { 0: 1 }; // key: 前缀和, value: 出现次数
  let currentPrefixSum = 0; // 当前的前缀和
  let totalCount = 0; // 满足和为 targetSum 的子数组数量

  for (let i = 0; i < nums.length; i++) {
    currentPrefixSum += nums[i]; // 更新前缀和

    // 如果存在前缀和 = 当前前缀和 - 目标和，则说明存在一个子数组的和为 targetSum
    if (prefixSumCountMap[currentPrefixSum - targetSum]) {
      totalCount += prefixSumCountMap[currentPrefixSum - targetSum];
    }

    // 更新前缀和出现次数
    if (prefixSumCountMap[currentPrefixSum]) {
      prefixSumCountMap[currentPrefixSum]++;
    } else {
      prefixSumCountMap[currentPrefixSum] = 1;
    }
  }

  return totalCount;
};

举例

nums = [1, 2, 3, 0, 3]
targetSum = 3

初始化

prefixSumCountMap = {0: 1}  // 前缀和 0 出现一次
currentPrefixSum = 0
totalCount = 0

---

第 1 步 (i = 0, nums[0] = 1)

currentPrefixSum = 0 + 1 = 1
prefixSumCountMap[1 - 3] = prefixSumCountMap[-2] 不存在 → totalCount = 0
更新前缀和出现次数: prefixSumCountMap[1] = 1

prefixSumCountMap = {0: 1, 1: 1}

没有子数组和为 3

---

第 2 步 (i = 1, nums[1] = 2)

currentPrefixSum = 1 + 2 = 3
prefixSumCountMap[3 - 3] = prefixSumCountMap[0] = 1 → totalCount += 1 → totalCount = 1
更新前缀和出现次数: prefixSumCountMap[3] = 1

prefixSumCountMap = {0: 1, 1: 1, 3: 1}

找到子数组 [1,2]

---

第 3 步 (i = 2, nums[2] = 3)

currentPrefixSum = 3 + 3 = 6
prefixSumCountMap[6 - 3] = prefixSumCountMap[3] = 1 → totalCount += 1 → totalCount = 2
更新前缀和出现次数: prefixSumCountMap[6] = 1

prefixSumCountMap = {0: 1, 1: 1, 3: 1, 6: 1}

找到子数组 [3]

---

第 4 步 (i = 3, nums[3] = 0)

currentPrefixSum = 6 + 0 = 6
prefixSumCountMap[6 - 3] = prefixSumCountMap[3] = 1 → totalCount += 1 → totalCount = 3
更新前缀和出现次数: prefixSumCountMap[6] = 2

prefixSumCountMap = {0: 1, 1: 1, 3: 1, 6: 2}

找到子数组 [3,0]

---

第 5 步 (i = 4, nums[4] = 3)

currentPrefixSum = 6 + 3 = 9
prefixSumCountMap[9 - 3] = prefixSumCountMap[6] = 2 → totalCount += 2 → totalCount = 5
更新前缀和出现次数: prefixSumCountMap[9] = 1

prefixSumCountMap = {0: 1, 1: 1, 3: 1, 6: 2, 9: 1}

找到子数组 [0,3] 和 [3]

---

最终结果

totalCount = 5

所有和为 3 的连续子数组：

[1,2], [3], [3,0], [0,3], [3]

矩阵

73.矩阵置零

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  var row = matrix.length;
  var col = matrix[0].length;

  var map1 = {};
  var map2 = {};

  for (var i = 0; i < row; i++) {
    for (var j = 0; j < col; j++) {
      if (matrix[i][j] === 0) {
        map1[i] = i;
        map2[j] = j;
      }
    }
  }

  for (var i in map1) {
    //取的是键
    for (var j = 0; j < col; j++) {
      matrix[i][j] = 0;
    }
  }

  for (var i in map2) {
    for (var j = 0; j < row; j++) {
      matrix[j][i] = 0;
    }
  }
  return matrix;
};

先扫描矩阵，记录下所有含 0 的行、列。

• 用 map1 保存“要清零的行号”
• 用 map2 保存“要清零的列号”

遍历 map1，把整行变 0。

遍历 map2，把整列变 0。

举例

输入矩阵：

matrix = [
  [1, 2, 3],
  [4, 0, 6],
  [7, 8, 9]
]

---

第一步：找出 0

逐行逐列检查：

• (0,0)=1 不是 0
• (0,1)=2 不是 0
• (0,2)=3 不是 0
• (1,0)=4 不是 0
• (1,1)=0 ✅ 找到 0 → 记录行=1，列=1
• (1,2)=6 不是 0
• (2,0)=7 不是 0
• (2,1)=8 不是 0
• (2,2)=9 不是 0

结果：

map1 = { 1: 1 }   // 第 1 行要清零
map2 = { 1: 1 }   // 第 1 列要清零

---

第二步：整行清零

对 map1 里的行（行号=1），把整行变 0：

[
  [1, 2, 3],
  [0, 0, 0],
  [7, 8, 9]
]

---

第三步：整列清零

对 map2 里的列（列号=1），把整列变 0：

[
  [1, 0, 3],
  [0, 0, 0],
  [7, 0, 9]
]

---

最终结果

[
  [1, 0, 3],
  [0, 0, 0],
  [7, 0, 9]
]

为什么用map--自动去重

if (matrix[i][j] === 0) {
  map1[i] = i;
  map2[j] = j;
}

📌 作用

其实作者只是想 记录哪些行、哪些列需要清零。

• map1 记录所有需要清零的行号
• map2 记录所有需要清零的列号

---

🤔 为什么用对象（map）？

因为对象的 键（key）天然去重。 比如：

• 如果一行有多个 0，你只需要记一次这个行号。
• 用数组的话可能会 push 多次，还要去重。
• 用对象就不会重复，map1[i] = i 多次赋值，还是同一个键。

所以这里用对象是为了 自动去重。

---

📌 为什么 键 = 值？

其实值根本没用！

• map1[i] = i 只是随手赋了个值
• 真正关心的是 对象的键 i
• 后面 for (var i in map1)，取的就是键。

所以它完全可以写成：

map1[i] = true;
map2[j] = true;

更语义化：表示第 i 行要清零。

---

✅ 总结

1. 用对象是为了 避免重复记录行号/列号

2. map1[i] = i 实际上“值”没用，只是为了保证对象里有这个键

3. 更好的写法是：

   map1[i] = true;
   map2[j] = true;

54.螺旋矩阵

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
const DIRS = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0],
]; // 右下左上

var spiralOrder = function (matrix) {
  const m = matrix.length,
    n = matrix[0].length;
  const ans = Array(m * n);
  //一共遍历这么多个数，就是矩阵有几个数，全都要走一遍
  let i = 0,
    j = 0,
    di = 0;
  for (let k = 0; k < m * n; k++) {
    // 一共走 mn 步
    ans[k] = matrix[i][j];
    matrix[i][j] = Infinity; // 标记为无穷，表示已经访问过（已经加入答案）
    const x = i + DIRS[di][0];
    const y = j + DIRS[di][1]; // 下一步的位置
    // 如果 (x, y) 出界或者已经访问过
    if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] === Infinity) {
      di = (di + 1) % 4; // 右转 90°
    }
    i += DIRS[di][0];
    j += DIRS[di][1]; // 走一步
  }
  return ans;
};

方向数组 DIRS

const DIRS = [[0,1], [1,0], [0,-1], [-1,0]];

这是一个“向量数组”，里面四个元素代表 坐标移动的方向。

• [0,1] → (行不变, 列+1) → 向右走
• [1,0] → (行+1, 列不变) → 向下走
• [0,-1] → (行不变, 列-1) → 向左走
• [-1,0] → (行-1, 列不变) → 向上走

转向逻辑：di = (di + 1) % 4

当你走到 边界 或者 下一个格子已经访问过，就要 右转 90°。 在代码里，“右转”就是把 di 顺时针加 1。

• di=0（右） → 转一次 → di=1（下）
• di=1（下） → 转一次 → di=2（左）
• di=2（左） → 转一次 → di=3（上）
• di=3（上） → 转一次 → di=4，但 4 % 4 = 0 → 又回到右

所以 (di + 1) % 4 就是 顺时针方向轮换。

因为方向数组 DIRS 只有 4 个方向（索引是 0,1,2,3）。 如果单纯用 di+1，在最后一个方向（di=3 → 上）再转一次，就会变成 di=4，超出数组下标范围。

所以用 模运算来循环：

• (0+1) % 4 = 1 ✅
• (1+1) % 4 = 2 ✅
• (2+1) % 4 = 3 ✅
• (3+1) % 4 = 4 % 4 = 0 → 自动回到第一个方向 ✅

这样就实现了 顺时针循环。

1. 矩阵坐标 (i, j)

在二维数组（矩阵）里：

• i 表示 行号（竖着数）
• j 表示 列号（横着数）

例子：

matrix = [
  [a, b, c],
  [d, e, f],
  [g, h, i]
]

• matrix[0][0] = a → 在 第 0 行，第 0 列
• matrix[1][2] = f → 在 第 1 行，第 2 列

👉 所以 (i, j) 就是“当前位置”。

---

2. 移动方向用“增量”表示

我们想从 (i, j) 向四个方向移动。

• 向右：行不变，列加 1 → (i, j+1) → 增量是 (0, +1)
• 向下：行加 1，列不变 → (i+1, j) → 增量是 (+1, 0)
• 向左：行不变，列减 1 → (i, j-1) → 增量是 (0, -1)
• 向上：行减 1，列不变 → (i-1, j) → 增量是 (-1, 0)

---

3. 用数组存四个方向

把这四个“增量”排成一个数组 DIRS：

const DIRS = [
  [0, 1],   // 右
  [1, 0],   // 下
  [0, -1],  // 左
  [-1, 0]   // 上
];

---

4. 用 di 来选择方向

di 表示当前方向的下标。

• di=0 → 取 DIRS[0] = [0,1] → (行+0, 列+1) = 向右
• di=1 → 取 DIRS[1] = [1,0] → (行+1, 列+0) = 向下
• di=2 → 取 DIRS[2] = [0,-1] → 向左
• di=3 → 取 DIRS[3] = [-1,0] → 向上

---

5. 更新位置

假设当前位置是 (i, j)，方向是 di。 那就：

i += DIRS[di][0]; // 行号的变化
j += DIRS[di][1]; // 列号的变化

举个例子：

• 如果 di=0（向右），那 DIRS[0] = [0,1] → i += 0, j += 1 → (i,j+1)
• 如果 di=1（向下），那 DIRS[1] = [1,0] → i += 1, j += 0 → (i+1,j)

完美对应“上下左右”。

48.旋转图像-转置

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {
  const n = matrix.length;
  // 第一步：转置
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      // 遍历对角线下方元素
      const tmp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = tmp;
    }
  }

  // 第二步：行翻转
  //每一行都是一个数组
  for (const row of matrix) {
    row.reverse();
  }
};

初始矩阵

matrix =
[
  [ 1,  2,  3,  4],
  [ 5,  6,  7,  8],
  [ 9, 10, 11, 12],
  [13, 14, 15, 16]
]

---

第一步：转置（沿主对角线翻转）

转置就是把 (i, j) 和 (j, i) 交换。

交换后矩阵：

[
  [ 1,  5,  9, 13],
  [ 2,  6, 10, 14],
  [ 3,  7, 11, 15],
  [ 4,  8, 12, 16]
]

第二步：行翻转（每一行反转）

把每一行倒过来（reverse）。

[
  [13,  9,  5,  1],
  [14, 10,  6,  2],
  [15, 11,  7,  3],
  [16, 12,  8,  4]
]

总结逻辑

1. 转置：把行和列交换 → 把旋转的“方向”转出来。
2. 行翻转：再把每行倒过来 → 完成顺时针 90°旋转。

240.探索二维矩阵2

前提：矩阵行列都是升序的

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  const m = matrix.length,
    n = matrix[0].length;
  //m是行，n是列
  let i = 0,
    j = n - 1; // 从右上角开始
  while (i < m && j >= 0) {
    // 还有剩余元素
    if (matrix[i][j] === target) {
      return true; // 找到 target
    }
    if (matrix[i][j] < target) {
      i++; // 这一行剩余元素全部小于 target，排除
    } else {
      j--; // 这一列剩余元素全部大于 target，排除
    }
  }
  return false;
};

复杂度分析 时间复杂度：O(m+n)，其中 m 和 n 分别为 matrix 的行数和列数。每次循环排除掉一行或者一列，一共 m+n 行列，最坏情况下需要排除 m+n−1 行列才能找到答案。 空间复杂度：O(1)

二分查找

35.探索插入位置easy

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

其实就是：

返回 nums 中的第一个（最左边的）大于或等于 target 的数的下标。如果所有数都小于 target，返回 nums 的长度。

区间其实是答案可能存在的索引范围

左闭右开区间法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0,
    right = nums.length; // [left, right)
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
};

复杂度分析

• 时间复杂度：O(logn)，其中 n 为 nums 的长度。
• 空间复杂度：O(1)，仅用到若干额外变量

举例分析

数组和目标：

nums = [1, 3, 5, 6], target = 5

目标：返回 最小的 i，使得 nums[i] >= target。 答案应该是 i = 2，因为 nums[2] = 5。

---

Step 1

初始化：

left = 0, right = 4   // 区间 [0,4)

计算：

mid = (0+4)/2 = 2
nums[2] = 5

比较：

• nums[mid] = 5 >= target = 5
• 所以 right = mid = 2

区间变为：

[left, right) = [0, 2)

---

Step 2

left = 0, right = 2
mid = (0+2)/2 = 1
nums[1] = 3

比较：

• 3 < 5
• 所以 left = mid+1 = 2

区间变为：

[left, right) = [2, 2)

---

Step 3

循环退出（因为 left = right）。 返回 left = 2

循环推进逻辑

在循环里，我们取：

mid = Math.floor((left + right) / 2)

然后比较 nums[mid] 和 target：

1. 如果 nums[mid] < target
   • 说明 mid 不可能是答案
   • 并且所有 ≤ mid 的下标都不是答案
   • 所以更新：left = mid + 1
   • 这时 [left, right) 缩小到了右半边
2. 否则（nums[mid] >= target）
   • 说明 mid 可能是答案
   • 但为了找到 最小的满足条件的下标，还要往左再试试
   • 所以更新：right = mid
   • 这时 [left, right) 缩小到了左半边

左闭右开与数组边界

数组的合法索引范围是 0 到 n-1。 在二分过程中，我们经常会用到 nums[mid]。 如果边界处理不当，就可能访问到 nums[n]（数组越界）。

闭区间 [left, right]

初始化：

let left = 0, right = nums.length - 1; // [0, n-1]

• 边界点 right = n-1 是数组最后一个元素的下标。

• 在循环里条件是 while (left <= right)，所以最后一次迭代可能会取到 mid = n-1。

• 更新后 left 可能变成 n：

  if (nums[mid] <= target) {
      left = mid + 1;  // 此时可能变成 left = n
  }

  只要循环条件仍是 left <= right 且 right 初始化为 n - 1，此时循环会结束，不会访问 nums[n]。

• 闭区间写法的关键是保持 [left, right] 的不变量：初始化 right = n - 1，排除 mid 时更新为 mid - 1 或 mid + 1。它本身并不比左闭右开写法更容易越界，混用两套边界规则才会出错。

左闭右开 [left, right)

初始化：

let left = 0, right = nums.length; // [0, n)

• 这里 right 本身就是一个“不可能的索引”（相当于哨兵），它表示“终点之后”。
• 在循环里条件是 while (left < right)，因此：
  • mid 永远会落在 [0, n-1] 范围内（因为 right 最大是 n）。
  • 即使最后收缩到 [n, n)，循环直接退出，根本不会去访问 nums[n]。
• 在保持 [left, right) 不变量的前提下，mid 始终是合法索引。空数组时循环不会进入，同样不会访问元素。

贪心算法

121.买卖股票的最佳时机easy

只能买一次，卖一次，要最大利润

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let ans = 0; // 最大利润，初始为 0（不买不亏）
  let minPrice = prices[0];
  // 记录历史最低价格，初始为第一天的价格
  for (const p of prices) {
    // 遍历每天的价格
    ans = Math.max(ans, p - minPrice); // 今天卖掉的利润 vs 历史最大利润
    minPrice = Math.min(minPrice, p); // 更新历史最低价格
  }
  return ans; // 返回最大利润
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为 prices 的长度。
• 空间复杂度：O(1)。仅用到若干额外变量。

内在逻辑分析

找一个最低价买入点，然后遍历过程中，随时计算“如果今天卖出能赚多少”，并记录最大利润。

• minPrice = 到目前为止见过的 最低买入价格
• p - minPrice = 假设今天卖出，能获得的利润
• ans = 历史上所有可能卖出的利润最大值

最终答案就是在整个过程中遇到的 最大利润。

贪心算法的关键思想：

局部最优 → 推出全局最优

在这个题里：

1. 局部最优选择： 每一天我只做两件事：
   • 更新买入的最低价（贪心地认为“历史上最便宜的一天买入”才可能赚最多）。
   • 更新最大利润（贪心地认为“今天卖出能赚最多时，就记下来”）。
2. 全局最优结果： 由于股票只能买卖一次，全局最优解必然是：
   • 在某个最低点买入
   • 在它之后的某个最高点卖出 我们的算法正好保证了这点。

---

对比直观理解

• 如果不用贪心，你可能会考虑“所有买卖组合”，时间复杂度 O(n²)。
• 用贪心，每天只看 今天的价格 和 历史最低价，一步步更新，就能 O(n) 得到最大利润。

这就是贪心的威力： 只要保证“每一步都不吃亏”，最后结果自然是最优的。

动态规划DP

动态规划的几个关键特征

1. 最优子结构

   • 大问题的解，可以通过小问题的解推出来。
   • 爬楼梯：到达第 i 阶的方法数 dp[i]，由 dp[i-1] 和 dp[i-2] 推出来。

2. 重叠子问题

   • 在递归过程中，会反复计算相同的子问题。
   • 例如：求 dp[5] 时要用 dp[4] 和 dp[3]； 而求 dp[4] 又会用到 dp[3] 和 dp[2] —— dp[3] 被重复使用。

3. 状态转移方程

   • 明确「状态」：这里状态就是“走到第 i 阶的方法数”。

   • 明确「转移」：如何从前面的状态推到当前状态。

   • 公式就是：

     dp[i] = dp[i-1] + dp[i-2]

4. 自底向上求解

   • 动态规划通常不是用递归暴力枚举，而是把小问题先算好，逐步推出大问题的解。
   • 爬楼梯就是从 dp[0]、dp[1] 开始，一步步推出 dp[n]。

---

套用到爬楼梯问题

• 问题：走到第 n 阶有多少种方法？
• 子问题：走到第 i 阶的方法数依赖于走到 i-1 和 i-2 阶。
• 状态转移：dp[i] = dp[i-1] + dp[i-2]
• 边界条件：dp[0] = 1, dp[1] = 1
• 最终答案：dp[n]

70.爬楼梯easy

你一次可以走 1 步 或 2 步，问到达第 n 阶台阶有多少种方法。

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  const dp = [];
  dp[0] = 1; // 站在地面，有 1 种“方法”（不动）
  dp[1] = 1; // 到第 1 阶，只有 1 种方法：走 1 步 dp = [1, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

核心公式

dp[i] = dp[i-1] + dp[i-2]

解释：

• dp[i-1] → 从 i-1 阶再走 1 步到 i 阶
• dp[i-2] → 从 i-2 阶再走 2 步到 i 阶 所以，总方法数就是两者之和。

动态规划公式的直觉：

• 我们要到 第 i 阶。
• 最后一步已经被“定死”了：要么 走 1 步（从 i-1 来），要么 走 2 步（从 i-2 来）。
• 所以只要知道：
  • 到达 i-1 的方法数（dp[i-1]），再加最后一步 +1
  • 到达 i-2 的方法数（dp[i-2]），再加最后一步 +2
• 这两种情况加起来，就是到达 i 阶的总方法数。

换句话说： 👉 站在终点往回看，路径只有两条分支：从 i-1 来 or 从 i-2 来。 👉 所以 dp[i] = dp[i-1] + dp[i-2]。

执行步骤（n = 5）

1️⃣ 初始化

dp[0] = 1   // 站在地面，有 1 种“方法”（不动）
dp[1] = 1   // 到第 1 阶，只有 1 种方法：走 1 步

此时：

dp = [1, 1]

---

2️⃣ 计算 i = 2

dp[2] = dp[1] + dp[0] = 1 + 1 = 2

解释：

• 最后一步走 1 阶 → 从第 1 阶来（1 种方法）
• 最后一步走 2 阶 → 从地面来（1 种方法）

所以到第 2 阶总共有 2 种方法：

(1+1), (2)

此时：

dp = [1, 1, 2]

---

3️⃣ 计算 i = 3

dp[3] = dp[2] + dp[1] = 2 + 1 = 3

解释：

• 最后一步走 1 阶 → 从第 2 阶来（2 种方法）
• 最后一步走 2 阶 → 从第 1 阶来（1 种方法）

所以到第 3 阶总共有 3 种方法：

(1+1+1), (1+2), (2+1)

此时：

dp = [1, 1, 2, 3]

---

4️⃣ 计算 i = 4

dp[4] = dp[3] + dp[2] = 3 + 2 = 5

解释：

• 从第 3 阶来（3 种）
• 从第 2 阶来（2 种）

所以到第 4 阶共有 5 种方法：

(1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2)

此时：

dp = [1, 1, 2, 3, 5]

---

5️⃣ 计算 i = 5

dp[5] = dp[4] + dp[3] = 5 + 3 = 8

解释：

• 从第 4 阶来（5 种）
• 从第 3 阶来（3 种）

所以到第 5 阶共有 8 种方法：

(1+1+1+1+1)
(1+1+1+2)
(1+1+2+1)
(1+2+1+1)
(2+1+1+1)
(2+2+1)
(2+1+2)
(1+2+2)

最终：

dp = [1, 1, 2, 3, 5, 8]

118.杨辉三角easy

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  const c = Array(numRows);
  // 准备一个长度为 numRows 的二维数组
  for (let i = 0; i < numRows; i++) {
    //遍历每一行 i，从第 0 行到第 numRows-1 行。
    c[i] = Array(i + 1);
    // 第 i 行有 i+1 个元素
    c[i][0] = c[i][i] = 1;
    // 每一行的两端都是 1
    for (let j = 1; j < i; j++) {
      //开始：j = 1 → 跳过第 0 个元素（首端 1）

      //结束：j < i → 不包含 i（尾端 1）
      // 左上方的数 + 正上方的数
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
  return c;
};

当 i=0 或 i=1：

• i=0 → 内层 for (1; 1<0) → 不执行
• i=1 → 内层 for (1; 1<1) → 不执行
• 正好符合杨辉三角的规律：前两行只有 1，不需要计算中间值

当 i=2：

• 内层循环 j=1
• c[2][1] = c[1][0] + c[1][1] → 正常计算中间值

技巧题

136.只出现一次的数字easy

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let res = 0;
  for (const num of nums) {
    res ^= num;
  }
  return res;
};

复杂度分析

时间复杂度 O(n)

• 代码里有一个 for 循环，遍历了 nums 数组的 每一个元素。
• 假设数组长度为 n，就会执行 n 次异或操作。
• 每次异或操作是 常数时间 O(1)，所以总时间就是 n × O(1) = O(n)。

空间复杂度 O(1)

• 除了 res 这个变量，我们没开额外的数组或哈希表。
• 不管 n 多大，只用常数个变量。
• 所以空间复杂度是 O(1)。

利用异或运算 a⊕a=0 的性质，我们可以用异或来「消除」所有出现了两次的元素，最后剩下的一定是只出现一次的元素。

例如 nums=[4,1,2,1,2]，把所有元素异或：

= 4⊕1⊕2⊕1⊕2 = 4⊕(1⊕1)⊕(2⊕2) = 4⊕0⊕0

=4

其中用到了异或运算的交换律 a⊕b=b⊕a，以及结合律 (a⊕b)⊕c=a⊕(b⊕c)（类比加法）。

代码中，初始化 ans=0 是因为 0⊕a=a，相当于我们从第一个数开始，和其它数异或。

169.多数元素easy

例子

输入：

nums = [2, 2, 1, 1, 1, 2, 2]

---

变量说明

• ans：当前的“候选擂主”。
• hp：候选者的生命值。
  • 如果遇到相同的数，hp 加 1（盟友帮忙回血）。
  • 如果遇到不同的数，hp 减 1（敌人打擂主）。
  • 如果 hp 变成 0，说明擂主被打下去了，换新擂主。

---

过程模拟（逐个遍历）

初始

ans = 0，hp = 0。

---

遍历 nums

1. x = 2

   • hp === 0，所以 ans = 2，hp = 1
   • 状态: ans=2, hp=1

   [2] (擂主=2, hp=1)

---

1. x = 2

   • x === ans，所以 hp = hp+1 = 2
   • 状态: ans=2, hp=2

   [2,2] (擂主=2, hp=2)

---

1. x = 1

   • x !== ans，所以 hp = hp-1 = 1
   • 状态: ans=2, hp=1

   [2,2,1] (擂主=2, hp=1)

---

1. x = 1

   • x !== ans，所以 hp = hp-1 = 0
   • 状态: ans=2, hp=0

   [2,2,1,1] (擂主=2被打下台, hp=0)

---

1. x = 1

   • hp === 0，换新擂主：ans=1, hp=1
   • 状态: ans=1, hp=1

   [2,2,1,1,1] (新擂主=1, hp=1)

---

1. x = 2

   • x !== ans，hp = hp-1 = 0
   • 状态: ans=1, hp=0

   [2,2,1,1,1,2] (擂主=1被打下台, hp=0)

---

1. x = 2

   • hp === 0，换新擂主：ans=2, hp=1
   • 状态: ans=2, hp=1

   [2,2,1,1,1,2,2] (新擂主=2, hp=1)

---

最终结果

ans = 2，返回 2

---

图像类比

把它想成 打擂台：

• 擂主有血量（hp）。
• 相同阵营的来帮擂主回血。
• 不同阵营的来消耗擂主血量。
• 当擂主血量归零，换人当擂主。
• 最后的擂主就是多数元素（因为如果有一个元素数量超过一半，它一定能活到最后）。

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let ans = 0,
    hp = 0;
  for (const x of nums) {
    if (hp === 0) {
      // x 是初始擂主，生命值为 1  这里注意是三等号
      ans = x;
      hp = 1;
    } else {
      // 比武，同门加血，否则扣血
      hp += x === ans ? 1 : -1; //这里注意是加血量
    }
  }
  return ans;
};

test