最长连续序列与 LRU Cache
使用集合以 O(n) 的时间解决最长连续序列问题，然后使用 OrderedDict 设计 LRU Cache。
最长连续序列与 LRU Cache 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
最长连续序列问题
LeetCode 128“最长连续序列”：给定一个未排序的数组，找出最长连续整数序列的长度。例如，[100,4,200,1,3,2] 包含长度为 4 的连续序列 [1,2,3,4]。挑战在于要在O(n) 而不是 O(n log n) 时间内解决问题（后者是先排序再扫描的复杂度）。
关键思路是：使用集合进行 O(1) 成员检查，并且只从序列的最小元素开始计数（通过检查前驱元素不在集合中来识别最小元素）。
def longestConsecutive(nums):
num_set = set(nums)
best = 0
for n in num_set:
if n - 1 not in num_set: # n is the start of a sequence
curr_n = n
length = 1
while curr_n + 1 in num_set:
curr_n += 1
length += 1
best = max(best, length)
return best
print(longestConsecutive([100,4,200,1,3,2])) # 4
print(longestConsecutive([0,3,7,2,5,8,4,6,0,1])) # 9为什么 O(n) 的证明成立
在外层 for 循环的所有迭代中，每个数字最多只会在 while 循环中被访问一次。虽然 for 循环内部包含一个 while 循环，但所有外层迭代中的 while 循环迭代总数最多为 n（因为每个数字最多只能作为一个序列的“curr_n + 1”）。这一摊销分析使整体复杂度达到 O(n)，与单调栈的分析类似。
# Demonstrate O(n) total inner iterations
nums = list(range(1000)) # worst case: one long sequence
num_set = set(nums)
inner_iters = 0
for n in num_set:
if n - 1 not in num_set:
curr = n
while curr + 1 in num_set:
curr += 1
inner_iters += 1
print('n =', len(nums), ' total inner iterations =', inner_iters)
# inner_iters = n-1 <= n => O(n)替代方案：基于排序的方法
作为对比，排序后扫描的方法运行复杂度为 O(n log n)：先对数组排序，去除连续重复项，然后统计连续区间。虽然速度较慢，但它使用 O(1) 额外空间（如果原地排序）。基于集合的方法使用 O(n) 额外空间。在面试中可以同时说明这两种方法，并根据空间限制阐明 O(n log n) 的方案是否可以接受。
def longestConsecutive_sort(nums):
if not nums:
return 0
nums.sort()
best = length = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
continue # skip duplicates
if nums[i] == nums[i-1] + 1:
length += 1
best = max(best, length)
else:
length = 1
return best
print(longestConsecutive_sort([100,4,200,1,3,2])) # 4什么是 LRU 缓存
LRU（最近最少使用）缓存是一种固定容量的数据结构。当缓存已满且需要插入新项目时，它会逐出最近最少使用的项目。操作包括：如果键存在，get(key) 返回对应值（并将其标记为最近使用）；如果键不存在，则返回 -1；put(key, value) 插入键值对（达到容量上限时逐出 LRU 项目）。
LRU 缓存用于操作系统（页面置换）、浏览器缓存和数据库查询缓存。LeetCode 146 要求您使用 O(1) 的 get 和 put 实现一个 LRU 缓存。
使用 OrderedDict 实现 LRU 缓存
Python 的 collections.OrderedDict 维护插入顺序，并支持使用 move_to_end(key)（O(1)）将项目标记为最近使用。在执行 put 时，将键移动到末尾；溢出时，弹出第一个项目（LRU 项目）。这样便可使用一个内部由双向链表和哈希映射支持的内置结构，以 O(1) 复杂度完成 get 和 put。
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict LRU (first item)
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1)) # 1 (and 1 becomes most recently used)
cache.put(3, 3) # evict key 2 (LRU)
print(cache.get(2)) # -1
cache.put(4, 4) # evict key 1 (LRU)
print(cache.get(1)) # -1
print(cache.get(3)) # 3
print(cache.get(4)) # 4从零实现 LRU 缓存：双向链表 + HashMap
从零实现的方案使用双向链表（支持 O(1) 节点删除）和哈希映射（通过键以 O(1) 查找节点）。链表按照从 LRU（head.next）到 MRU（tail.prev）的顺序维护项目。虚拟头节点和尾节点充当哨兵，可以消除在边界处插入和删除时的特殊情况。
class DNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCacheDLL:
def __init__(self, capacity):
self.cap = capacity
self.map = {} # key -> DNode
self.head = DNode() # dummy LRU end
self.tail = DNode() # dummy MRU end
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_tail(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_to_tail(node)
return node.val
def put(self, key, val):
if key in self.map:
self._remove(self.map[key])
node = DNode(key, val)
self._add_to_tail(node)
self.map[key] = node
if len(self.map) > self.cap:
lru = self.head.next
self._remove(lru)
del self.map[lru.key]
cache = LRUCacheDLL(2)
cache.put(1,1); cache.put(2,2)
print(cache.get(1)) # 1
cache.put(3,3)
print(cache.get(2)) # -1 (evicted)为什么 LRU 使用双向链表
如果不知道前驱节点，单向链表就无法在 O(1) 时间内删除任意节点。双向链表同时存储 prev 和 next 指针，因此只要给定节点引用，就能在 O(1) 时间内完成删除。哈希映射则提供通过键以 O(1) 访问节点的能力。两者结合后：get(key) 需要 O(1) 查找节点，并需要 O(1) 将其移动到尾部；put(key) 需要 O(1) 添加节点，并需要 O(1) 从头部删除 LRU 节点。
# Why not a singly linked list?
# To remove a node you need its predecessor
# With SLL: must traverse from head to find predecessor => O(n)
# With DLL: node.prev IS the predecessor => O(1) removal
print('SLL removal: O(n) — must find predecessor by traversal')
print('DLL removal: O(1) — node.prev is immediately available')
print('Hash map lookup: O(1) — get DNode reference by key')
print('Combined LRU get/put: O(1) average')LFU 缓存（最不经常使用）
更复杂的一种变体是 LFU 缓存（LeetCode 460），其中访问次数最少的项目会被逐出。如果访问次数相同，则按最近使用情况打破平局（在访问频率最低的项目中，逐出最近最少使用的项目）。实现需要三种数据结构：键到值的映射、键到频率的映射，以及频率到 OrderedDict 的映射（用于维护每个频率分组内的插入顺序）。LFU 的 get 和 put 的摊销复杂度为 O(1)。
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.min_f = 0
self.kv = {} # key -> val
self.kf = {} # key -> freq
self.fk = defaultdict(OrderedDict) # freq -> {key: None}
def _touch(self, key):
f = self.kf[key]
self.kf[key] = f + 1
del self.fk[f][key]
if not self.fk[f] and f == self.min_f:
self.min_f += 1
self.fk[f+1][key] = None
def get(self, key):
if key not in self.kv:
return -1
self._touch(key)
return self.kv[key]
def put(self, key, val):
if self.cap == 0: return
if key in self.kv:
self.kv[key] = val
self._touch(key)
else:
if len(self.kv) == self.cap:
lfu_key, _ = self.fk[self.min_f].popitem(last=False)
del self.kv[lfu_key]; del self.kf[lfu_key]
self.kv[key] = val; self.kf[key] = 1
self.fk[1][key] = None; self.min_f = 1设计模式：哈希映射 + 链表
LRU 缓存展示了一种强大的设计模式：将用于 O(1) 键查找的哈希映射，与用于 O(1) 有序操作的链表结合起来。这种模式会出现在多个面试设计问题中：LRU 缓存、LFU 缓存、跳表以及某些队列变体。只要问题同时要求 O(1) 查找和 O(1) 基于顺序的操作，就可以考虑这种组合。
在面试中明确说明这一模式，可以体现您进行系统级思考的能力，以及对经典数据结构组合的熟悉程度。
矩阵中的连续序列
这是将连续序列思想扩展到二维的情况：给定一个整数矩阵，找出能够沿路径追踪的最长连续序列的长度（每一步移动到相邻单元格）。这会结合 BFS/DFS 与连续序列的集合方法。存储每个值的位置，然后对于每个起始值，检查值加 1 的元素是否存在于相邻位置。
# Simpler: find longest consecutive values in a 2D matrix (no adjacency)
def longestConsecutiveMatrix(matrix):
all_vals = set()
for row in matrix:
for v in row:
all_vals.add(v)
best = 0
for v in all_vals:
if v - 1 not in all_vals: # start of sequence
length = 0
while v in all_vals:
v += 1
length += 1
best = max(best, length)
return best
m = [[1, 5, 3], [4, 6, 2], [8, 7, 9]]
print(longestConsecutiveMatrix(m)) # 9 (1..9 all present)面试总结：集合 + HashMap 的力量
这两个问题体现了一个共同主题：使用正确的哈希结构，将 O(n log n) 或 O(n²) 问题转化为 O(n) 问题。最长连续序列使用集合以 O(1) 回答“前驱是否存在？”；LRU 缓存使用哈希映射即时找到节点，再使用双向链表以 O(1) 更新顺序。两者都用 O(1) 的成员检查或查找替代了缓慢的遍历。
当面试官问“您能做到优于 O(n log n) 吗？”时，答案几乎总是“使用哈希映射或哈希集合来避免排序”。
快速检查
请测试您对本课数据结构与算法 — 编程面试准备相关概念的理解。
课程回顾
本课您学到了：最长连续序列通过使用集合进行 O(1) 成员检查，并且只从序列起点开始计数，从而以 O(n) 运行，LRU 缓存通过 OrderedDict（或从零实现的哈希映射加双向链表）以 O(1) 完成 get 和 put，以及哈希映射加链表模式是构建对顺序敏感的 O(1) 数据结构时可复用的基础模块。接下来我们将使用基本情况、信任和构建框架重新学习递归。
常见问题解答
「最长连续序列与 LRU Cache」课时是免费的吗？
是的 — 「最长连续序列与 LRU Cache」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「最长连续序列与 LRU Cache」这节课中我会学到什么？
使用集合以 O(n) 的时间解决最长连续序列问题，然后使用 OrderedDict 设计 LRU Cache。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「最长连续序列与 LRU Cache」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 哈希函数原理与冲突处理
- 两数之和及其多种变体
- 频率统计与分组
- 最长连续序列与 LRU Cache