哈希表

相同组大小的人可以放在一起，但一个桶不一定就是一个组。用两个连续版本理解容量分组，并学会验证不唯一的答案。

用 Python 从两个字符串的异位词判断出发，先写出逐组扫描的正确解，再推导排序键与字符计数键，理解哈希表分组为什么成立。

重复的是文件内容，返回的却是完整路径。通过五个连续检查点，把输入解析、正确分组、哈希优化和平台提交串起来。

副标题 / 摘要 LeetCode 105 的关键不是死记“前序 + 中序能构树”，而是先看懂两种遍历各自提供什么信息。前序负责告诉你谁是根，中序负责告诉你左右边界，组合起来就能自然落成一个哈希定位的区间分治。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、分治、哈希表、前序遍历 SEO 关键词：Construct Binary Tree from Preorder and Inorder Traversal, 从前序与中序遍历序列构造二叉树, 前序遍历, 中序遍历, 分治, LeetCode 105 元描述：系统讲透 LeetCode 105 的构树推导、索引分治、哈希优化与多语言实现，并解释为什么一定要先建左子树。 A — Algorithm（题目与算法） 题目还原 给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder，请你重建这棵二叉树并返回它的根节点。 题目保证： 树中元素没有重复 给出的两个数组一定来自同一棵合法二叉树 输入输出 名称 类型 描述 preorder int[] 前序遍历结果 inorder int[] 中序遍历结果 返回值 TreeNode 重建后的二叉树根节点 示例 1 输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出：[3,9,20,null,null,15,7] 示例 2 输入：preorder = [-1], inorder = [-1] 输出：[-1] 提示 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 都没有重复元素 inorder 中的每个值都出现在 preorder 中 preorder 保证是某棵树的前序遍历 inorder 保证是同一棵树的中序遍历 目标读者 一看到“根据遍历结果构树”就会混淆前序和中序职责的学习者 想把“树的遍历顺序”和“树的结构恢复”建立稳定联系的开发者 做过 94、114 之后，想继续巩固树结构题的读者 背景 / 动机 这题最值得学的地方是： ...

副标题 / 摘要 Clone Graph 不是单纯的图遍历题，而是“带环对象图的深拷贝”题。真正的关键不是能不能走完图，而是如何保证每个原节点只克隆一次，并且所有边都指向克隆图中的新节点。 预计阅读时长：12~15 分钟 标签：图、DFS、BFS、哈希表、深拷贝 SEO 关键词：克隆图, Clone Graph, 图深拷贝, LeetCode 133, DFS, BFS 元描述：通过“原节点 -> 新节点”映射表实现无向图深拷贝，讲清 DFS/BFS、环处理、复杂度与多语言代码。 目标读者 刷 LeetCode 图论题、希望掌握“深拷贝 + visited/map”模板的学习者 需要复制对象图、工作流图、拓扑结构的工程师 经常在“图遍历”和“对象复制”之间混淆的开发者 背景 / 动机 很多同学第一次做这题，会把它当成普通遍历题： DFS 一遍 BFS 一遍 把值抄过去 但真正难点在于： 图里可能有环 同一个节点可能从多条路径访问到 复制出来的新图，所有邻居必须指向“新节点”，不能混入旧节点引用 所以这题本质上是： 带环对象图的深拷贝问题 这类模式在工程里也很常见： 复制流程编排图 克隆编辑器里的节点网络 复制依赖关系图做快照 核心概念 深拷贝：返回的新图里每个节点都必须是新建对象 节点身份：判断“是不是同一个节点”看的是对象身份 / 引用，不只是 val 邻接关系保持：新图的边结构必须与原图完全一致 映射表：原节点 -> 克隆节点，既防止死循环，也防止重复创建 A — Algorithm（题目与算法） 题目重述 给定一个无向连通图中某个节点 node 的引用，请返回这个图的深拷贝。 每个节点结构如下： class Node { public int val; public List<Node> neighbors; } 题目测试用例使用邻接表表示图。 如果图不为空，给定节点总是值为 1 的节点。 ...

副标题 / 摘要 这题不是“背答案题”，而是缓存系统的基本功：如何在常数时间内同时满足“快速访问”和“按最近最少使用淘汰”。本文从朴素方案推到最优结构，并给出可运行的多语言实现。 预计阅读时长：14~18 分钟 标签：LRU、哈希表、双向链表、系统设计 SEO 关键词：LRU Cache, LeetCode 146, 哈希表, 双向链表, O(1) 元描述：通过哈希表 + 双向链表实现 LRU 缓存，get/put 平均 O(1)，附工程场景、常见坑与六语言实现。 A — Algorithm（题目与算法） 题目重述 设计并实现一个满足 LRU 约束的数据结构 LRUCache： LRUCache(int capacity)：用正整数容量初始化 int get(int key)：若 key 存在返回 value，否则返回 -1 void put(int key, int value)： key 已存在：更新 value，并视作最近使用 key 不存在：插入新键值对 若超出容量：淘汰最久未使用的 key 并要求 get 和 put 平均时间复杂度为 O(1)。 示例 1（操作序列） LRUCache cache = new LRUCache(2) cache.put(1, 1) // 缓存: {1=1} cache.put(2, 2) // 缓存: {1=1, 2=2} cache.get(1) // 返回 1，且 1 变成最近使用 cache.put(3, 3) // 容量满，淘汰 key=2 cache.get(2) // 返回 -1 cache.put(4, 4) // 淘汰 key=1 cache.get(1) // 返回 -1 cache.get(3) // 返回 3 cache.get(4) // 返回 4 示例 2（更新已有键） LRUCache cache = new LRUCache(2) cache.put(1, 10) cache.put(1, 99) // 更新 value，且 1 视作最近使用 cache.get(1) // 返回 99 目标读者 正在刷 LeetCode 中等题、想吃透“数据结构组合技”的同学 做后端/中间件，需要实现或优化本地缓存的工程师 面试中经常被问到 LRU，但只记住结论、没掌握细节的人 背景 / 动机 缓存是“空间换时间”，但空间是有限的。 当缓存满了，必须淘汰一些键。LRU（Least Recently Used，最近最少使用）假设： ...

副标题 / 摘要 这道题的难点不是遍历链表，而是正确复制 random 指针所形成的“跨节点引用关系”。本文从朴素思路推导到哈希映射法，讲清为什么它稳定、可维护、易工程落地。 预计阅读时长：12~16 分钟 标签：链表、深拷贝、哈希表、随机指针 SEO 关键词：LeetCode 138, Copy List with Random Pointer, 随机链表复制, 深拷贝, 哈希映射 元描述：用两趟遍历 + 映射表完成随机链表深拷贝，系统讲解正确性、复杂度、工程实践与六语言实现。 A — Algorithm（题目与算法） 题目重述 给定一个长度为 n 的链表，每个节点有： val next random（可指向任意节点或 null） 要求构造该链表的深拷贝并返回新头节点。 新链表中的任何指针都不能指向原链表节点。 输入 / 输出表示 题面常用 [val, random_index] 表示每个节点： val：节点值 random_index：random 指向的节点下标；若为空则为 null 你的函数入参只有 head，输出复制链表的头节点。 示例 1 输入: [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出: [[7,null],[13,0],[11,4],[10,2],[1,0]] 解释: 输出与输入的“值与引用关系”一致，但节点是全新对象。 示例 2 输入: [[1,1],[2,1]] 输出: [[1,1],[2,1]] 解释: 第一个节点 random 指向第二个节点，第二个节点 random 指向自己。 目标读者 刷 LeetCode 时对 random 指针题目不够稳的开发者 想厘清“浅拷贝 vs 深拷贝”差异的同学 希望把算法思路迁移到工程对象复制场景的工程师 背景 / 动机 普通链表只要复制 val 和 next，逻辑很直观； 但随机链表多了一个 random 指针，它可能： ...

副标题 / 摘要 “路径不必从根开始、但必须向下”使得这题无法用简单的根到叶 DP 解决。本文用 ACERS 结构讲透 树上前缀和：把任意向下路径转化为“两个前缀和的差”，用哈希表在线计数，做到 O(n) 一次 DFS 统计所有答案。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、前缀和、DFS、哈希表 SEO 关键词：Path Sum III, 路径和 III, 树上前缀和, 前缀和哈希, LeetCode 437, Hot100 元描述：前缀和 + 哈希表在线统计二叉树向下路径和等于 targetSum 的条数，包含推导、复杂度对比与多语言实现。 目标读者 刷 LeetCode、希望把“树 + 哈希”题型沉淀成模板的学习者 对“路径不从根开始”的树题容易写成 O(n^2) 的同学 做日志调用链 / 层级数据分析，需要在树结构上做区间统计的工程师 背景 / 动机 很多“树上的路径问题”都有一个坑： 你以为要从根出发、或要到叶子结束，但题目允许 从任意节点开始、到任意节点结束（但方向必须向下）。 这意味着： 你不能只维护“从根到当前”的一种状态就完事； 也不能枚举所有起点（那会退化成 O(n^2)）； 更不能用滑动窗口（节点值可正可负，窗口单调性不存在）。 这题最值得掌握的点是：把“树上任意向下路径”化为“同一路径上的两个前缀和之差”。 一旦你掌握了这个模型，很多树上统计题都会变成“前缀和 + 哈希表”的熟悉配方。 核心概念 向下路径：只能从父到子（不能回头、不能跨分支） 前缀和（prefix sum）：从根到当前节点路径上所有节点值的累加 差分计数：若 curSum - prevSum = target，则 prevSum = curSum - target 路径内哈希表：只统计“当前 DFS 路径上的前缀和”，回溯时必须撤销（否则会把不同分支混在一起） A — Algorithm（题目与算法） 题目还原 给定一个二叉树的根节点 root 和整数 targetSum，求二叉树里 节点值之和等于 targetSum 的向下路径 的数目。 路径不需要从根节点开始，也不需要在叶子节点结束，但路径方向必须向下（只能从父节点到子节点）。 ...

副标题 / 摘要 最小覆盖子串是“可变滑动窗口 + 计数哈希表”的经典题。本文按 ACERS 模板解释如何判断窗口有效、如何收缩得到最短答案，并给出工程场景与多语言实现。 预计阅读时长：12~15 分钟 标签：滑动窗口、哈希表、字符串 SEO 关键词：Minimum Window Substring, 最小覆盖子串, 滑动窗口, 哈希表 元描述：最小覆盖子串的 O(n) 滑动窗口解法与工程应用，含多语言实现。 目标读者 正在刷 LeetCode 的中级开发者 需要掌握“可变窗口 + 覆盖约束”的算法模板 做文本分析、日志聚合或流式过滤的工程师 背景 / 动机 “在一段序列中找到最短区间覆盖目标集合”在工程中非常常见： 日志告警需要覆盖多种错误码，搜索摘要需要覆盖关键字， 运营分析需要覆盖多个行为标签。 本题提供了一个可复用的窗口收缩模板。 核心概念 可变滑动窗口：右指针扩张直到满足条件，左指针收缩缩短答案 计数哈希表：支持重复字符，必须按次数覆盖 满足条件的计数：判断当前窗口是否“覆盖了全部需要” A — Algorithm（题目与算法） 题目重述 给定字符串 s 和 t，返回 s 中最短的子串，使其包含 t 中的每一个字符（包括重复字符）。 若不存在这样的子串，返回空字符串 ""。 测试用例保证答案唯一。 输入输出 名称 类型 描述 s string 源字符串 t string 目标字符串（需要覆盖的字符与次数） 返回 string 最短覆盖子串或空串 示例 1 s = "ADOBECODEBANC", t = "ABC" 输出 = "BANC" 示例 2 s = "a", t = "a" 输出 = "a" 示例 3 s = "a", t = "aa" 输出 = "" C — Concepts（核心思想） 方法类型 可变滑动窗口 + 频次覆盖判断。 ...

副标题 / 摘要 这是 Hot100 专栏第 1 篇：和为 K 的子数组。本文用“前缀和 + 频次哈希表”把 O(n^2) 降到 O(n)，并按 ACERS 模板给出工程场景与多语言实现。 预计阅读时长：12~15 分钟 标签：Hot100、前缀和、哈希表 SEO 关键词：Subarray Sum Equals K, 和为K的子数组, 前缀和, 哈希表, O(n) 元描述：和为 K 的子数组计数问题的前缀和解法，含工程迁移、复杂度对比与多语言代码。 目标读者 正在刷 Hot100，希望建立稳定算法模板的初学者 需要把计数类算法迁移到业务数据统计的中级工程师 准备面试，想掌握“前缀和 + 哈希表”核心套路的人 背景 / 动机 “统计和为 K 的子数组数量”是最经典的计数类问题之一。 它广泛出现在日志分析、风控阈值命中、交易序列统计等场景。 朴素的两层遍历虽然直观，但一旦数据规模增大就会明显卡顿，因此需要可扩展的 O(n) 解法。 核心概念（必须理解） 子数组：数组中连续、非空的片段 前缀和：prefix[i] = nums[0..i] 的和 差分关系：若 prefix[r] - prefix[l-1] = k，则 nums[l..r] 的和为 k 频次哈希表：统计某个前缀和出现的次数，以 O(1) 均摊时间查询 A — Algorithm（题目与算法） 题目还原 给你一个整数数组 nums 和一个整数 k，请统计并返回 和为 k 的子数组 的个数。 子数组是数组中元素的连续非空序列。 ...