数组、链表与基础结构

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

先掌握切片、指针和 map；下列每个 package main 单独保存为 main.go，使用独立模块，不能拼成一个文件。本轮仅静态推导输出。容器为单线程练习，MinHeap.Pop 与 Stack.Pop 都要求非空；区间操作要求 0 <= l <= r <= n，整数累计须不溢出。

要解决的问题	可选方法	选择前确认
按下标读取或在中间插入	数组或链表	数组访问 O(1) 但插入要移动；链表已知节点后插入 O(1)，按位置查找仍为 O(n)。
按到达顺序、反向顺序或优先级取元素	队列、栈、双端队列、堆	堆只保证根最小；队列需处理已消费空间，固定容量双端队列需检查空满。
按键统计或定位	哈希表	平均查找和更新 O(1)，遍历顺序未定义；稳定展示需排序键。
反复求静态区间和或批量做区间加法	前缀和或差分数组	前缀和适合静态查询；差分先记录全部更新再还原，不适合每次更新后立即查询。
避免重复扫描连续区间或配对	滑动窗口或双指针	示例窗口长度固定；目标和双指针要求数组有序，排序时须考虑原下标。
按最近使用顺序淘汰缓存，或分配分片归属	LRU 缓存或一致性哈希	LRU 的 map 与链表须同步；哈希环需注意节点分布不均和虚拟节点。

按下标、节点、键或行列访问数据

数组

正文、推演与完整示例：数组。

Go 切片提供连续下标访问，append 可能因容量不足而分配新底层数组。示例先扩展长度，再用 copy 将插入位置后的元素右移。 按下标访问 O(1)，中间插入需移动元素，时间 O(n)。

插入下标必须在合法范围内；频繁在中间插入时，移动成本可能比查找成本更重要。

链表

正文、推演与完整示例：链表。

节点只保存值和下一个节点的指针，插入时改写相邻指针即可。示例已持有目标节点，因此操作不需要遍历；若只知道下标，仍要从头走到该位置。 已知节点后插入 O(1)，按位置查找 O(n)。

链表会产生额外指针与分配开销，Go 中普通顺序数据通常优先用切片。

哈希表

正文、推演与完整示例：哈希表。

Frequencies 用字符串作键，遇到一次就把计数加一。Go 的 map 在读取不存在的键时返回零值，因此无需预先插入每个单词。 查找与更新平均为 O(1)。

平均查找很快，但迭代顺序未定义；需要稳定输出时应先排序键。

矩阵遍历

正文、推演与完整示例：矩阵遍历。

涉及邻居搜索时还要检查行列边界，尤其是各行长度不同的情况。

控制先进先出、后进先出与优先级

栈

正文、推演与完整示例：栈。

Push 把值附加到切片末尾，Pop 读取并删除最后一个值，保持后进先出。解析括号、深度优先搜索和撤销记录都可用栈。 尾部入栈摊还 O(1)。

示例假设弹出时非空；正式 API 应返回成功标记或错误，避免空栈越界。

队列

正文、推演与完整示例：队列。

长期运行时要定期压缩或重置底层切片，否则已消费的前段可能继续占内存。

双端队列

正文、推演与完整示例：双端队列。

环形缓冲区把逻辑位置映射到固定长度数组，front 左移即可在头部插入。尾部下标由 front 与 size 计算，两个方向都不必搬动已有元素。 两端都支持插入和取出。

这个示例要求容量大于零且未满；实际容器还需处理扩容和空队列。

堆

正文、推演与完整示例：堆。

最小堆只保证根是最小值，不保证整个切片有序。Push 沿父节点向上调整，Pop 把末尾元素放到根后沿较小子节点向下调整。 插入与取最小值都是 O(log n)。

优先队列和 Top K 常用堆；访问任意非根元素仍可能要线性查找。

预处理区间和与批量区间更新

前缀和

正文、推演与完整示例：前缀和。

它适合静态数据；频繁修改元素时应使用树状数组或线段树。

差分数组

正文、推演与完整示例：差分数组。

对 [l,r) 加 delta，只需在 l 处加 delta、r 处减 delta。所有更新记录完后做一次前缀累加，即可恢复每个位置的最终值。 n 个元素、q 次更新的总处理时间为 O(n+q)。

它适合离线批量更新；若更新之间要立即查询，应换用支持在线操作的数据结构。

用指针和窗口减少重复扫描

双指针

正文、推演与完整示例：双指针。

有序数组的左右端相加后，和太小就移动左指针，太大就移动右指针。每一步都排除不可能的配对，因此只需线性扫描。 示例查找有序数组中的目标和。

输入无序时必须先排序或改用哈希表，并注意是否还需要原始下标。

滑动窗口

正文、推演与完整示例：滑动窗口。

先计算第一个固定长度窗口的和，随后每右移一步只减去离开的元素并加上新进入的元素。这样避免重复求和，使整体复杂度降为 O(n)。 示例求长度为 k 的最大区间和，总时间 O(n)。

可变长度窗口需要明确扩张与收缩条件；这个示例只处理固定 k。

维护缓存淘汰顺序与分片归属

LRU 缓存

正文、推演与完整示例：LRU 缓存。

map 让键能直接定位链表节点，链表头表示最近使用、尾部表示最久未使用。Get 与 Put 都把访问项移到头部；容量超限时删除尾节点。 Go 示例使用 container/list。

这里的 LRU 缓存用 map 定位 container/list 的节点。Get 命中和 Put 更新时调用链表的 MoveToFront，把节点移到最近使用端；淘汰时先删除 map 中的键，再用 Remove 删除同一尾节点，两个结构须保持一致。这两个方法属于链表，不是 LRU 自己新增的对外 API。

两个结构必须同步更新，否则会出现悬挂索引或错误淘汰。

一致性哈希

正文、推演与完整示例：一致性哈希。

节点分布不均时会产生倾斜，实践中常为每个真实节点设置多个虚拟节点。

静态自检

对容量为 2 的 LRU 依次 Put(a)、Put(b)、Get(a)、Put(c)，预测哪个键消失。提示：Get 也改变最近使用顺序。

参考解法

b 被淘汰；Get(a) 使 a 回到表头，随后新增 c 从尾部淘汰 b。仅调整 map、不同步移动或删除链表节点会破坏不变量。