模板速查

何时用：反复查询「区间和」，且数组不变

function buildPrefix(nums) {
  // preSum[i] = nums 前 i 个元素的和（不含 nums[i]）
  const preSum = new Array(nums.length + 1).fill(0);   // 🚨 长度 n+1
  for (let i = 0; i < nums.length; i++) {
    preSum[i + 1] = preSum[i] + nums[i];
  }
  return preSum;
}

// 闭区间 [i, j] 的和
const rangeSum = (preSum, i, j) => preSum[j + 1] - preSum[i];

何时用：反复对「区间整体加减」，最后才看结果

function increment(diff, i, j, val) {
  diff[i] += val;
  if (j + 1 < diff.length) diff[j + 1] -= val;
}

何时用：「连续子串/子数组」且窗口扩大时性质单调

function slidingWindow(s) {
  const window = new Map();
  let left = 0, right = 0;

  while (right < s.length) {
    const c = s[right];
    right++;                       // 扩大窗口
    // ... 把 c 加进窗口，更新窗口内的数据

    while (/* 窗口需要收缩 */) {
      const d = s[left];
      left++;                      // 缩小窗口
      // ... 把 d 移出窗口，更新窗口内的数据
    }
  }
}

何时用：有序数组里找某个值在不在

function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;   // 闭区间 [left, right]

  while (left <= right) {                  // 区间非空的条件
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

何时用：有重复值，要第一个 ≥ target 的位置

// 左边界：第一个 >= target 的位置（不存在则返回 nums.length）
function lowerBound(nums, target) {
  let left = 0, right = nums.length;       // 🚨 开区间右端，注意不是 n-1
  while (left < right) {                   // 🚨 配 <
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;                      // 🚨 不是 mid - 1
  }
  return left;
}

// 右边界：第一个 > target 的位置
function upperBound(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] <= target) left = mid + 1;   // 只差这个 <=
    else right = mid;
  }
  return left;
}

何时用：求「最小的最大值」这类，且可行性单调

function shipWithinDays(weights, days) {
  // 判定：载重 cap 能否在 days 天内运完
  const feasible = (cap) => {
    let need = 1, cur = 0;
    for (const w of weights) {
      if (cur + w > cap) { need++; cur = 0; }
      cur += w;
    }
    return need <= days;
  };

  // 🚨 下界是「最重的那件货」——比它小的载重连一件都装不下
  let left = Math.max(...weights);
  // 上界是「全部货物总重」——一天运完，一定可行
  let right = weights.reduce((a, b) => a + b, 0);

  while (left < right) {                    // 就是 lowerBound
    const mid = left + Math.floor((right - left) / 2);
    if (feasible(mid)) right = mid;         // 可行 → 试试更小的
    else left = mid + 1;
  }
  return left;
}

何时用：数组整体无序，但只旋转过一次

function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {                 // 左半 [lo, mid] 有序
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                                      // 那右半 [mid, hi] 必然有序
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

何时用：完全无序，但每步能判断「哪边必有答案」

function findPeak(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;   // 上坡 → 右边必有峰
    else hi = mid;                                  // 下坡 → 左边（含 mid）必有峰
  }
  return lo;
}

何时用：对每个元素找左/右第一个更大或更小的

function nextGreaterElement(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = [];                 // 存下标，栈内对应的值单调递减

  for (let i = 0; i < nums.length; i++) {
    // 当前元素比栈顶大 → 它就是栈顶那些元素的「下一个更大」
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      res[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return res;                       // 栈里剩下的没有更大元素，保持 -1
}

何时用：固定宽度窗口滑过去，每个位置要最值

function maxSlidingWindow(nums, k) {
  const res = [];
  const dq = [];                    // 存下标，对应的值单调递减

  for (let i = 0; i < nums.length; i++) {
    // ① 队尾：比新元素小的都没机会了，弹掉
    while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);

    // ② 队头：滑出窗口了就弹掉
    if (dq[0] <= i - k) dq.shift();

    // ③ 窗口形成后，队头就是最大值
    if (i >= k - 1) res.push(nums[dq[0]]);
  }
  return res;
}

何时用：「所有操作 O(1)」的设计题；哈希表 + 双链表

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();                    // key → 节点
    // ⭐ 哨兵头尾，省掉所有空链表/单元素的边界判断
    this.head = { key: null, val: null };    // head.next 是最近使用的
    this.tail = { key: null, val: null };    // tail.prev 是最久未使用的
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;
    this._remove(node);        // 摘下来
    this._addToFront(node);    // 挪到最前 = 标记为最近使用
    return node.val;
  }

  put(key, val) {
    const existing = this.map.get(key);
    if (existing) {
      existing.val = val;
      this._remove(existing);
      this._addToFront(existing);
      return;
    }
    if (this.map.size === this.cap) {
      const lru = this.tail.prev;            // 最久未使用
      this._remove(lru);
      this.map.delete(lru.key);              // 🚨 别忘了从 map 里也删
    }
    const node = { key, val };
    this._addToFront(node);
    this.map.set(key, node);
  }
}

何时用：返回值一物两用：要么是找到的目标，要么是答案

function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;    // 两边各找到一个 → 当前节点就是答案
  return left ?? right;              // 只有一边有 → 把它原样往上报
}

何时用：给遍历序列反推树；全局游标 + 只切中序区间

function buildPreIn(preorder, inorder) {
  const pos = new Map();
  inorder.forEach((v, i) => pos.set(v, i));   // 值 → 中序下标，把「找根」降到 O(1)
  let p = 0;                                   // 前序游标，全局只走一遍

  function build(lo, hi) {                     // 负责中序区间 [lo, hi]
    if (lo > hi) return null;
    const val = preorder[p++];                 // 前序当前项就是这棵子树的根
    const node = { val, left: null, right: null };
    const i = pos.get(val);
    node.left = build(lo, i - 1);              // ⚠️ 必须先左后右
    node.right = build(i + 1, hi);
    return node;
  }
  return build(0, inorder.length - 1);
}

何时用：要「所有方案」，且答案是一条条走出来的路径

function permute(nums) {
  const res = [], track = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (track.length === nums.length) {
      res.push([...track]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;          // 这个数已经在路径里了

      track.push(nums[i]);            // 做选择
      used[i] = true;

      backtrack();

      track.pop();                    // 撤销选择
      used[i] = false;
    }
  }

  backtrack();
  return res;
}

何时用：求最短步数，且每步代价相同

function bfs(start, target, neighborsOf) {
  const q = [start];
  const visited = new Set([start]);
  let step = 0;
  let head = 0;                       // 下标当队头，别用 shift()

  while (head < q.length) {
    const sz = q.length - head;       // 🚨 先存下来，同层序遍历
    for (let i = 0; i < sz; i++) {
      const cur = q[head++];

      if (cur === target) return step; // ⭐ 第一次碰到就是最短，见下

      for (const next of neighborsOf(cur)) {
        if (visited.has(next)) continue;
        visited.add(next);            // 🚨 入队时就标记，不是出队时
        q.push(next);
      }
    }
    step++;                            // 一层走完，步数加一
  }

  return -1;
}

何时用：带非负权的最短路；BFS 换成优先队列

function dijkstra(start, n, adj) {
  // dist[i] = 从 start 到 i 的最短距离，未知先设为 Infinity
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  const pq = new MinHeap();            // 见下方实现
  pq.push([0, start]);                 // [距离, 节点]

  while (pq.size > 0) {
    const [d, u] = pq.pop();

    // 🚨 这一行是关键，不能省。见下方「为什么不需要 visited」
    if (d > dist[u]) continue;

    for (const [v, w] of adj[u]) {
      const nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        pq.push([nd, v]);
      }
    }
  }

  return dist;
}

何时用：要任意两点间的距离；点少（≲400）时最省事，且支持负权

function floyd(n, edges) {
  // d[i][j] = i 到 j 的最短距离；自己到自己是 0，其余先设为不可达
  const d = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));

  for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);  // 重边取小的

  // 🚨 k 必须在最外层。为什么见下一节 —— 这是全篇唯一需要背的东西
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

  return d;
}

何时用：分治的标准骨架；也是求逆序对的底子

function mergeSort(nums) {
  if (nums.length <= 1) return nums;         // base case

  const mid = nums.length >> 1;
  const left = mergeSort(nums.slice(0, mid));   // 分解 + 解决
  const right = mergeSort(nums.slice(mid));

  return merge(left, right);                    // 合并
}

function merge(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) res.push(a[i++]);      // ⚠️ 这个 = 号见下
    else res.push(b[j++]);
  }
  while (i < a.length) res.push(a[i++]);
  while (j < b.length) res.push(b[j++]);
  return res;
}

何时用：只要第 k 大，不用全排序

function findKthLargest(nums, k) {
  const target = nums.length - k;          // 第 k 大 = 升序里的下标 n-k
  let lo = 0, hi = nums.length - 1;
  while (true) {
    const p = partition(nums, lo, hi);     // 复用上面那个 partition
    if (p === target) return nums[p];
    if (p < target) lo = p + 1;            // 目标在右边，左边整段丢掉
    else hi = p - 1;
  }
}

何时用：每个物品选或不选，容量有上限

function knapsack01(W, weights, values) {
  const n = weights.length;
  // dp[i][w] = 只看前 i 个物品、容量为 w 时的最大价值
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      if (weights[i - 1] > w) {
        dp[i][w] = dp[i - 1][w];                  // 装不下，只能不拿
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],                                        // 不拿
          dp[i - 1][w - weights[i - 1]] + values[i - 1],       // 拿
        );
      }
    }
  }

  return dp[n][W];
}

何时用：子序列类 DP 的模板；注意不是子串

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;

  // dp[i] = 以 nums[i] 结尾的最长递增子序列长度
  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);       // 🚨 不是 dp[n-1]
}

何时用：反复问「这两个在不在一组」、动态合并

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);   // 各自成一个集合
    this.count = n;                                          // 连通分量个数
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x];         // 一路往上找根
    return x;
  }

  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;      // 本来就在一个集合里
    this.parent[rx] = ry;
    this.count--;                     // 合并一次，分量数减一
    return true;
  }

  connected(x, y) { return this.find(x) === this.find(y); }
}

何时用：大量字符串的前缀查询

class Trie {
  constructor() { this.root = { children: new Map(), isEnd: false }; }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, { children: new Map(), isEnd: false });
      }
      node = node.children.get(ch);
    }
    node.isEnd = true;                // 🚨 走完才标记
  }

  // 沿着 word 走，走不通返回 null
  _walk(word) {
    let node = this.root;
    for (const ch of word) {
      node = node.children.get(ch);
      if (node === undefined) return null;
    }
    return node;
  }

  search(word) { const n = this._walk(word); return n !== null && n.isEnd; }

  startsWith(prefix) { return this._walk(prefix) !== null; }
}

何时用：单点改 + 区间和，两个操作都要 log n

class BIT {
  constructor(n) { this.n = n; this.t = new Array(n + 1).fill(0); }

  add(i, delta) {                                  // 单点加
    for (; i <= this.n; i += i & -i) this.t[i] += delta;
  }

  sum(i) {                                         // 前缀和 [1, i]
    let s = 0;
    for (; i > 0; i -= i & -i) s += this.t[i];
    return s;
  }

  range(l, r) { return this.sum(r) - this.sum(l - 1); }   // ⭐ 区间靠相减
}

何时用：字符串匹配；next 本身也能解重复子串类题

function buildNext(p) {
  const next = new Array(p.length).fill(0);
  let len = 0;                    // 当前「最长相等前后缀」的长度

  for (let i = 1; i < p.length; i++) {
    // 🚨 失配就往回跳，而不是直接归零
    while (len > 0 && p[i] !== p[len]) len = next[len - 1];

    if (p[i] === p[len]) len++;
    next[i] = len;
  }
  return next;
}

何时用：要拿很多子串互相比；把「相等」变成 O(1) 的数值比较

function hashOf(s) {
  let h = 0;
  for (let i = 0; i < s.length; i++) h = (h * BASE + s.charCodeAt(i)) % MOD;
  return h;
}

何时用：两个乘数都是 mod 量级时。⚠️ 直接写 a*b%m 在 JS 里 78% 的情况会算错

function mulmod(a, b, m) {
  const ah = Math.floor(a / 65536), al = a % 65536;
  return ((ah * b % m) * 65536 + al * b) % m;
}

何时用：滚动哈希做匹配；单模式串其实不如 indexOf，学它是为了滚动那一步

function rabinKarp(s, p) {
  const n = s.length, m = p.length;
  if (m === 0) return 0;
  if (m > n) return -1;

  let pow = 1;
  for (let i = 0; i < m - 1; i++) pow = pow * BASE % MOD;   // BASE^(m-1)

  let hp = 0, hs = 0;
  for (let i = 0; i < m; i++) {
    hp = (hp * BASE + p.charCodeAt(i)) % MOD;
    hs = (hs * BASE + s.charCodeAt(i)) % MOD;
  }

  for (let i = 0; ; i++) {
    // ⭐ 哈希相等只是「疑似」，逐字符复核之后才敢返回
    if (hs === hp && s.substr(i, m) === p) return i;
    if (i + m >= n) break;

    // 🚨 这里是 + MOD，不是 + MOD * MOD
    //    后者 1e18 越过 2^53 —— 我第一版就这么写的，3000 组错了 2190 组
    hs = ((hs - s.charCodeAt(i) * pow % MOD + MOD) % MOD * BASE
          + s.charCodeAt(i + m)) % MOD;
  }
  return -1;
}