LeetCode 138 https://leetcode.cn/problems/copy-list-with-random-pointer/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 简单的做法是直接用一个哈希表把两个链表中节点的对应关系存起来，在二次遍历的时候设置新链表的 next 和 random。 此外，我们可以把新链表和旧链表混在一起。依次复制每个节点（创建新节点并复制 val 和 next），把新节点直接插到原节点的后面，形成一个交错链表。如此一来，原链表节点的下一个节点，就是其对应的新链表节点了！ 然后遍历这个交错链表，假如节点 1 的 random 指向节点 3，那么就把节点 1′ 的 random 指向节点 3 的下一个节点 3′，这样就完成了对 random 指针的复制。 最后，从交错链表链表中分离出深拷贝后的链表。 时间复杂度：O(n)，其中 n 是链表的长度。 空间复杂度：O(1)。返回值不计入。 ...
LeetCode 460 https://leetcode.cn/problems/lfu-cache/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是 LRU 缓存的升级版。本题对于每个使用频率，都需要维护一个双向链表，并通过哈希表把频率和链表关联起来。为了找到最少的使用频率，需要维护一个 min_freq 变量。 在插入时需要插入到链表的头部，而当容量满，需要删除时需要删除的是最少使用频率的书中的尾部结点 dummy->prev。 时间复杂度：所有操作均为 O(1)。 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。 ...
LeetCode 560 https://leetcode.cn/problems/subarray-sum-equals-k/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是前缀和题目。需要注意只有满足单调性的时候才能使用滑动窗口。 s 为前缀和，如果 i 到 j 的和为 k，那么 s[j] - s[i] == k。 枚举右，维护左，通过哈希表统计有多少 s[i] == s[j] - k。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(n)。 ...
LeetCode 128 https://leetcode.cn/problems/longest-consecutive-sequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 对于 nums 中的元素 x，以 x 为起点，不断查找下一个数 x+1,x+2,⋯ 是否在 nums 中，并统计序列的长度。 为了做到 O(n) 的时间复杂度，需要两个关键优化： 把 nums 中的数都放入一个哈希集合中，这样可以 O(1) 判断数字是否在 nums 中。 如果 x−1 在哈希集合中，则不以 x 为起点。为什么？因为以 x−1 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长！这样可以避免大量重复计算。比如 nums=[3,2,4,5]，从 3 开始，我们可以找到 3,4,5 这个连续序列；而从 2 开始，我们可以找到 2,3,4,5 这个连续序列，一定比从 3 开始的序列更长。 ⚠ 注意：遍历元素的时候，要遍历哈希集合，而不是 nums！如果 nums=[1,1,1,…,1,2,3,4,5,…]（前一半都是 1），遍历 nums 的做法会导致每个 1 都跑一个 O(n) 的循环，总的循环次数是 \(O(n^2)\)，会超时。 时间复杂度：O(n)，其中 n 是 nums 的长度。在二重循环中，每个元素至多遍历两次：在外层循环中遍历一次，在内层循环中遍历一次。所以二重循环的时间复杂度是 O(n) 的。比如 nums=[1,2,3,4]，其中 2,3,4 不会进入内层循环，只有 1 会进入内层循环。 空间复杂度：O(n)。 ...
LeetCode 76 https://leetcode.cn/problems/minimum-window-substring/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这是滑动窗口的题目。s 覆盖 t 的意思就是对 t 中的每个字母，s 里的出现次数都不小于 t 里的出现次数。出现次数使用哈希表来计数，在本题可以使用数组来进行优化。 时间复杂度：O(∣Σ∣m+n)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。注意 left 只会增加不会减少，left 每增加一次，我们就花费 O(∣Σ∣) 的时间。因为 left 至多增加 m 次，所以二重循环的时间复杂度为 O(∣Σ∣m)，再算上统计 t 字母出现次数的时间 O(n)，总的时间复杂度为 O(∣Σ∣m+n)。 空间复杂度：O(∣Σ∣)。如果创建了大小为 128 的数组，则 ∣Σ∣=128。 ...
LeetCode 1 https://leetcode.cn/problems/two-sum/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ LeetCode 第一题，哈希表的应用。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(n)。哈希表需要 O(n) 的空间。 ...
LeetCode 146 https://leetcode.cn/problems/lru-cache/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是双向链表和哈希表的经典题目。每个节点有 key，value，还有两个指针 prev 和 next 分别指向前一个和下一个节点。 此外，链表中还包含一个 dummy 节点，让每个节点的 prev 和 next 都不为空。 时间复杂度：所有操作均为 O(1)。 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。 ...
LeetCode 0003 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 难度：中等 本题为经典的哈希表加滑动窗口的题目，哈希表统计窗口内字符出现次数，如果窗口右端点字符出现次数大于 1，右移左端点，直到无重复字符，最后更新答案。窗口的长度为 right - left + 1。 时间复杂度：O(n)，其中 n 为 s 的长度。注意 left 至多增加 n 次，所以整个二重循环至多循环 O(n) 次。 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为 ASCII 字符，所以 ∣Σ∣≤128。 ...