LeetCode 零散笔记

LRU

核心结构：哈希表 + 双向链表。

• 哈希表负责 O(1) 查找节点。
• 双向链表负责维护访问顺序。
• 最近访问的节点移动到链表头部。
• 超出容量时删除链表尾部节点。

两数之和 / 和为 K 的子数组

这类题通常优先考虑哈希表。

思路区别：

• 两数之和：记录已经出现过的数，判断 target - nums[i] 是否存在。
• 和为 K 的子数组：使用前缀和，记录每个前缀和出现次数。

前缀和

前缀和题目要特别注意初始化：

map.put(0, 1);

含义：在还没有遍历任何元素时，前缀和为 0 出现过一次。

如果不加这一步，从数组开头开始、和刚好为 k 的子数组会被漏掉。

路径总和

题目链接：路径总和 III

常见思路：

• 双重递归：外层枚举每个节点作为起点，内层向下统计路径和。
• 前缀和：记录从根节点到当前节点的路径和，查询是否存在 currentSum - targetSum。

如果先追求直观理解，可以先掌握双重递归；如果追求更高效率，再使用前缀和优化。