leetcode 题型

leetcode 上的题目有很多是题型类似的，形变而神不变。

数组

双指针

滑动窗口

二分

栈

队列 -> bfs

const queue = []
while (queue.length) {
    const len = queue.length
    for (let i = 0; i < len; ++i) {
        // ...
    }
}

堆

function sink(arr, start, end) {

}

字符串

哈希

原地哈希

原地哈希是一种利用数组自身作为哈希表的技巧，将数组中的每个元素映射到其值对应的索引位置上。当题目满足以下条件时适用：数组长度为 n，元素值在 [1, n] 或 [0, n-1] 范围内（即值域与索引域恰好一一对应），且需要对元素进行存在性判断、查找或去重。

核心思想：遍历数组，将每个元素交换到它"应该在"的索引位置上，即 nums[i] 应该放在 nums[nums[i] - 1] 的位置（值域为 [1, n] 的情况）。经过一轮遍历后，每个索引 i 上的值就是 i + 1（如果不缺失的话），此时可以直接通过索引来查找元素是否存在，无需额外的哈希表。

// 原地哈希：将每个元素放到对应的索引位置
function inPlaceHash(nums) {
  for (let i = 0; i < nums.length; i++) {
    // nums[i] 应该放在索引 nums[i] - 1 的位置
    while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]) {
      [nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]];
    }
  }
  // 此时如果 nums[i] !== i + 1，说明 i + 1 不在数组中
}

典型题目及思路：

• 找缺失的数（LeetCode 268、448）：原地哈希后，nums[i] !== i + 1 的位置对应的 i + 1 就是缺失的数。448 题要求找出所有缺失的数，直接遍历一遍收集结果即可。
• 找重复的数（LeetCode 287）：原地哈希过程中，如果发现 nums[i] 对应的目标位置已经放了相同的值，说明 nums[i] 就是重复的数。
• 找首次出现的正数（LeetCode 41）：原地哈希后，第一个 nums[i] !== i + 1 的位置，i + 1 就是答案。
• 判断是否为排列（LeetCode 41 变体）：原地哈希后，检查每个位置是否满足 nums[i] === i + 1。

原地哈希的时间复杂度为 O(n)，空间复杂度为 O(1)。之所以能做到 O(1) 空间，是因为利用了题目给定的值域范围约束——值域恰好可以映射到索引域，数组本身就充当了哈希表的角色。这是"不使用额外数据结构"类题目的常见优化方向。

链表

图

dfs/bfs

dfs 使用递归，构造 dfs 递归函数

bfs 使用队列，使用队列进行迭代搜索

矩阵

并查集

拓扑排序

统计入度： 计算图中所有节点的入度。 初始化队列： 将所有入度为 0 的节点放入队列。 循环处理：从队列中弹出一个节点 $u$，将其加入结果序列。遍历 $u$ 的所有邻居节点 $v$。将 $v$ 的入度减 1（模拟删除边 $(u,v)$）。如果 $v$ 的入度变为 0，则将 $v$ 放入队列。 结果判断： 如果最终结果序列中的节点数等于图中的总节点数，则排序成功；否则，说明图中存在环。

排列组合

DP

子数组

前缀和、划分型 DP