罗罗编程学习记录
本页内容 展开查看

02.9.1.1 链表与数组高频 20 题

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.9 高频题单 / 02.9.1 高频题单与解题路线

本页为索引串联型题单:每题给出一句话思路、复杂度口径、易错点与本库关联页面,完整推导见关联页面。

02.9.1.1-001 两数之和(LC 1)

一句话结论

哈希表存已遍历值到下标,遍历到当前数时查 target - 当前值 是否在表中,一次遍历得到两数下标。

概念解释

考点:哈希查找;时间 O(n),空间 O(n)。

原理流程

  1. 边遍历边存 value→index。
  2. 查补数是否已出现。
  3. 命中返回下标对。

代码 / 示例

关联:哈希表设计与冲突处理

常见误区

  • 误区:先排序再双指针;正解:题目要求下标,排序破坏下标,用哈希。
  • 误区:先存全表再查;正解:边遍历边查可同时处理重复值场景。

追问

  • Q:两数有重复值怎么办? A:哈希存最新下标,题目保证唯一解即可。
  • Q:有序数组两数之和? A:对撞指针 O(1) 空间,见 02.9.1.4-001。

02.9.1.1-002 三数之和(LC 15)

一句话结论

排序后固定一个数,余下区间对撞双指针;固定值去重 + 左右指针去重,跳过重复三元组。

概念解释

考点:排序 + 双指针 + 三层去重;时间 O(n²),空间 O(1)(不计排序与结果)。

原理流程

  1. 排序。
  2. i 固定,l=i+1, r=n-1 按和移动。
  3. 命中后跳过重复 l、r,i 层也去重。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:只去重固定值;正解:l、r 命中后也要跳过相同值。
  • 误区:和大于目标时移动 l;正解:有序下和偏大应收缩 r。

追问

  • Q:四数之和思路? A:再外层固定一层,同套双指针去重。
  • Q:复杂度瓶颈? A:排序 O(n log n),枚举 O(n²)。

02.9.1.1-003 盛最多水的容器(LC 11)

一句话结论

左右对撞指针,水量由较矮边界决定;每次移动较矮一侧指针,期望找到更高边界提升容量。

概念解释

考点:对撞指针;时间 O(n),空间 O(1)。

原理流程

  1. l=0, r=n-1。
  2. 面积 = min(h[l],h[r]) × 宽度。
  3. 移动较矮一侧,更新最大面积。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:移动较高一侧;正解:较高侧保留,移动矮侧才可能抬高短板。
  • 误区:宽度每次减一但忘记取 min 高度。

追问

  • Q:为什么移动矮侧不丢最优解? A:矮侧已作为短板,换高侧宽度减小而短板不变,容量不会更大。
  • Q:与接雨水区别? A:接雨水逐格累计积水,本题是两板夹容器。

02.9.1.1-004 合并两个有序数组(LC 88)

一句话结论

nums1 尾部留有空间,双指针从后往前填,避免从前到后覆盖未读元素。

概念解释

考点:逆序双指针;时间 O(m+n),空间 O(1)。

原理流程

  1. 三指针:i=m-1, j=n-1, k=m+n-1。
  2. 取较大值放 k。
  3. 剩余段直接复制。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:从前到后合并;正解:会覆盖 nums1 未读前缀,必须倒序。
  • 误区:j 耗尽后忘记复制 nums1 前缀。

追问

  • Q:空间 O(n) 写法? A:辅助数组合并后拷回。
  • Q:与合并有序链表区别? A:数组倒序填坑,链表用哑节点串联。

02.9.1.1-005 删除有序数组重复项(LC 26)

一句话结论

快慢指针:慢指向下一个保留位置,快指针扫描;与慢前值不同则写入慢位并推进。

概念解释

考点:快慢指针原地删除;时间 O(n),空间 O(1)。

原理流程

  1. slow=0。
  2. fast 扫描,新值写入 slow。
  3. 返回 slow 长度。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:用额外集合去重;正解:有序下相邻比较即可原地完成。
  • 误区:返回数组长度写成 slow+1 口径错误。

追问

  • Q:允许保留两个重复项(LC 80)? A:比较 slow-2 位置即可。
  • Q:无序数组去重? A:需排序或哈希,复杂度上升。

02.9.1.1-006 移动零(LC 283)

一句话结论

快慢指针:慢指向下一个非零应放位置,快指针遇到非零就交换到慢位并推进慢位。

概念解释

考点:快慢指针稳定分区;时间 O(n),空间 O(1)。

原理流程

  1. slow=0。
  2. fast 遇非零交换 a[slow]、a[fast],slow++。
  3. 零自然沉到末尾。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:先统计零再补零;正解:一次遍历交换完成且保序。
  • 误区:非零元素相对顺序被打乱。

追问

  • Q:写操作次数最少? A:直接覆盖非零后尾部补零,交换次数更少。
  • Q:与颜色分类区别? A:本题两类,颜色分类三类三指针。

02.9.1.1-007 最长无重复字符子串(LC 3)

一句话结论

滑动窗口 + 字符最后出现位置;右指针扩展,出现重复时左边界跳到重复位置之后。

概念解释

考点:滑窗 + 哈希;时间 O(n),空间 O(字符集)。

原理流程

  1. 记 last[char]。
  2. 右扩,重复则 left = max(left, last+1)。
  3. 更新最长长度。

代码 / 示例

关联:滑动窗口模板与边界

常见误区

  • 误区:左边界逐位收缩;正解:可直接跳到上次出现位置之后。
  • 误区:left 被回退;正解:取 max(left, 重复位+1)。

追问

  • Q:窗口何时收缩? A:不满足无重复条件时。
  • Q:复杂度口径? A:每字符进窗出窗各一次 O(n)。

02.9.1.1-008 和为 K 的子数组(LC 560)

一句话结论

前缀和 + 哈希计数:prefix[j] - prefix[i] = K,扫描时查 当前前缀和 - K 出现次数。

概念解释

考点:前缀和 + 哈希;时间 O(n),空间 O(n)。

原理流程

  1. 前缀和累加,哈希存前缀和出现次数。
  2. 查 sum-K 计数累加答案。
  3. 当前前缀和入哈希。

代码 / 示例

关联:前缀和与差分

常见误区

  • 误区:正数数组才可用滑窗;正解:含负数必须前缀和哈希。
  • 误区:忘记前缀和 0 出现一次的初始化。

追问

  • Q:子数组要求连续吗? A:是,前缀和差对应连续段。
  • Q:二维版本? A:行列前缀和 + 哈希枚举边。

02.9.1.1-009 最小覆盖子串(LC 76)

一句话结论

滑窗计数:右扩满足所需字符,左缩到不满足前记录最短窗口;用缺口计数判断是否覆盖。

概念解释

考点:滑窗 + 计数表;时间 O(n),空间 O(字符集)。

原理流程

  1. 统计目标字符需求。
  2. 右扩更新计数,缺口归零后左缩。
  3. 记录最短起止。

代码 / 示例

关联:滑动窗口模板与边界

常见误区

  • 误区:每次窗口都全表比对;正解:用缺口变量 O(1) 判断覆盖。
  • 误区:左缩时忘记回退计数。

追问

  • Q:与无重复子串区别? A:本题要求覆盖目标集合,可含多余字符。
  • Q:复杂度? A:左右指针各移动一次 O(n)。

02.9.1.1-010 螺旋矩阵(LC 54)

一句话结论

维护上下左右边界,按右、下、左、上顺序遍历,每走一边收缩边界并复查越界。

概念解释

考点:矩阵模拟;时间 O(mn),空间 O(1)(结果除外)。

原理流程

  1. 四边初始化。
  2. 顺时针四方向循环。
  3. 收缩边界并判合法。

代码 / 示例

关联:数学与模拟技巧

常见误区

  • 误区:收缩后不复查越界导致重复访问。
  • 误区:非方阵中间剩单行/单列时方向处理错误。

追问

  • Q:生成螺旋矩阵(LC 59)? A:同框架按顺序填值。
  • Q:边界变量有哪些? A:top、bottom、left、right。

02.9.1.1-011 反转链表(LC 206)

一句话结论

迭代三指针 prev/cur/next,逐个把 cur 指向 prev;或递归从尾节点反向挂载。

概念解释

考点:指针重连;时间 O(n),空间 O(1)(递归 O(n) 栈)。

原理流程

  1. prev=null, cur=head。
  2. 存 next,cur.next=prev,前移。
  3. prev 为新头。

代码 / 示例

关联:单链表基础操作与反转

常见误区

  • 误区:改指针前未存 next 导致断链。
  • 误区:递归返回值未作为新头向上传递。

追问

  • Q:递归怎么写? A:反转子链后把尾节点接到自己。
  • Q:反转前 n 个(LC 92)? A:记录后继节点断开再反转子段。

02.9.1.1-012 环形链表 II(LC 142)

一句话结论

快慢指针相遇后,慢指针与头节点同速前进,再次相遇即环入口;快慢路程差推导入口位置。

概念解释

考点:快慢指针 + 数学;时间 O(n),空间 O(1)。

原理流程

  1. 快两步慢一步,相遇判环。
  2. 一指针回起点,同速走。
  3. 相遇点为入口。

代码 / 示例

关联:相交环检测与快慢指针

常见误区

  • 误区:相遇点就是环入口;正解:相遇后需再同速定位入口。
  • 误区:无环时快指针空指针解引用。

追问

  • Q:为什么同速再走能到入口? A:路程差推导得入口到相遇点与起点到入口距离关系。
  • Q:环长度怎么求? A:相遇后再走一圈计数。

02.9.1.1-013 合并两个有序链表(LC 21)

一句话结论

哑节点挂结果,双指针取较小节点接入,剩余段直接接上。

概念解释

考点:哑节点 + 有序合并;时间 O(a+b),空间 O(1)。

原理流程

  1. dummy 哑节点。
  2. 两指针取小接入。
  3. 剩余段链接。

代码 / 示例

关联:哑节点哨兵与合并排序

常见误区

  • 误区:不用哑节点单独处理头节点;正解:dummy 统一接入逻辑。
  • 误区:接入后未推进对应指针。

追问

  • Q:合并 K 个链表? A:分治或堆选最小头节点,见 02.3.2.4。
  • Q:递归写法? A:取较小头,其余递归合并。

02.9.1.1-014 删除倒数第 N 个节点(LC 19)

一句话结论

快指针先走 N 步,再快慢同速;快到尾时慢位于倒数第 N+1,删其后继。

概念解释

考点:快慢指针;时间 O(n),空间 O(1)。

原理流程

  1. fast 前移 N 步。
  2. 同速到 fast 为尾。
  3. slow.next 跳过目标节点。

代码 / 示例

关联:相交环检测与快慢指针

常见误区

  • 误区:删除头节点时无哑节点导致空指针。
  • 误区:快指针先走步数与 N 差一。

追问

  • Q:为什么用哑节点? A:统一删除头节点与中间节点逻辑。
  • Q:一趟扫描还是两趟? A:快慢一趟完成。

02.9.1.1-015 两两交换链表节点(LC 24)

一句话结论

哑节点 + 前驱指针,每两个节点反转连接,前驱接到新的第二节点,整组推进。

概念解释

考点:哑节点 + 局部重连;时间 O(n),空间 O(1)。

原理流程

  1. dummy 接 head。
  2. 记录两个待交换节点与后继。
  3. 重连后前驱前进两组。

代码 / 示例

关联:哑节点哨兵与合并排序

常见误区

  • 误区:断链前未存后继节点。
  • 误区:奇数个节点时末尾处理遗漏。

追问

  • Q:K 个一组反转(LC 25)? A:计数分组,组内反转后接回。
  • Q:递归写法? A:交换前两个,剩余递归接上。

02.9.1.1-016 排序链表(LC 148)

一句话结论

快慢指针找中点断链,归并排序两半,再有序合并;自顶向下 O(n log n)。

概念解释

考点:链表归并;时间 O(n log n),空间 O(log n) 递归栈(迭代可 O(1))。

原理流程

  1. 快慢找中点切断。
  2. 递归排序两半。
  3. 合并有序链表。

代码 / 示例

关联:哑节点哨兵与合并排序

常见误区

  • 误区:中点用慢指针一步走到底;正解:快指针起步不同避免偶数节点环。
  • 误区:断链位置错误导致两半重叠。

追问

  • Q:为什么链表用归并不用快排? A:链表随机访问差,归并断链合并自然。
  • Q:自底向上归并? A:按块大小迭代合并,空间 O(1)。

02.9.1.1-017 LRU 缓存(LC 146)

一句话结论

哈希表定位节点 + 双向链表维护访问顺序;命中移到表头,超容量删表尾;get/put 均 O(1)。

概念解释

考点:哈希 + 双向链表;时间 O(1),空间 O(capacity)。

原理流程

  1. map 存 key→链表节点。
  2. 访问命中删旧位置插表头。
  3. 满则删表尾并移除映射。

代码 / 示例

关联:双向链表 LRU 与跳表

常见误区

  • 误区:只用哈希或只用链表;正解:定位 O(1) 与顺序维护 O(1) 需两者配合。
  • 误区:删除表尾节点后忘记同步移除哈希映射。

追问

  • Q:LRU 与 LFU 区别? A:LFU 按使用频率,需多级桶。
  • Q:链表为什么双向? A:删节点需前驱,单向 O(n) 找前驱。

02.9.1.1-018 相交链表(LC 160)

一句话结论

两指针各遍历本链表,走到头后切换到另一链表头;路程补齐后相遇即交点,无交点则同时为 null。

概念解释

考点:双指针路程抵消;时间 O(a+b),空间 O(1)。

原理流程

  1. pa、pb 各走本链。
  2. 到头切换到另一链头。
  3. 相遇返回节点。

代码 / 示例

关联:相交环检测与快慢指针

常见误区

  • 误区:用栈逆序比较;正解:双指针切换路程更省空间。
  • 误区:相交判断只比值;正解:比节点引用相同。

追问

  • Q:两链长度不同为什么切换有效? A:各自路程都为 a+b,同步到达交点。
  • Q:无交点终止条件? A:两指针同时为 null。

02.9.1.1-019 回文链表(LC 234)

一句话结论

快慢找中点,反转后半段,双指针逐值比较;可在比较后恢复链表。

概念解释

考点:快慢 + 反转;时间 O(n),空间 O(1)。

原理流程

  1. 快慢定位中点。
  2. 反转后半部分。
  3. 前后两段逐位比对。

代码 / 示例

关联:单链表基础操作与反转

常见误区

  • 误区:复制到数组再双指针;正解:额外 O(n),原地法更优。
  • 误区:奇偶长度下中点切分位置错误。

追问

  • Q:需要恢复原链表吗? A:题目一般不要求,工程上可反转回后半段。
  • Q:快慢起点怎么设? A:slow=head, fast=head,偶数长度切后半段。

02.9.1.1-020 数组中第 K 大元素(LC 215)

一句话结论

最小堆维护 K 个最大元素,或快速选择分区;堆 O(n log K),快选平均 O(n)、最坏 O(n²)。

概念解释

考点:堆 / 快速选择;时间见口径,空间 O(K)(堆)或 O(1)(快选迭代)。

原理流程

  1. 堆:超 K 弹出最小。
  2. 快选:分区缩窄到第 K 位。

代码 / 示例

关联:去重布隆过滤器与 Top-K 堆、堆排序与工程排序

常见误区

  • 误区:全排序后取第 K;正解:O(n log n) 可优化到堆或快选。
  • 误区:第 K 大用最大堆还是最小堆混淆;正解:维护 K 个最大用最小堆。

追问

  • Q:数据流第 K 大? A:固定大小最小堆持续维护。
  • Q:快选最坏怎么避免? A:随机选基准,期望 O(n)。