S03-X01 · 题解索引（LeetCode 1–100 + 笔记卡）

定位：附录型索引，可跳读。每题一行：题号 · 模式 · 时间/空间 · 一句话洞察 · 精讲位置。
前置：S03-B01–B09。
覆盖旧文：104 张题解卡（12,119 个原文点位），含 25 张空壳卡（补写在 J 系列）。
上一篇：S03-B09 · 数学算法集：从阶乘到 FFT
下一篇：S03-J01 · 双指针与滑动窗口。

用法：做不出题时先查这里拿到"模式"，再去对应 J 文章看完整推导与代码。只背答案不学模式，换马甲就废。

1. 双指针与滑动窗口（精讲 J01）

题	名称	时间 / 空间	一句话洞察
3	无重复最长子串	O(n) / O(Σ)	右指针扩张，左指针收缩到窗口内无重复
5	最长回文子串	O(n²) / O(1)	每个中心（奇/偶）向两侧扩；要 O(n) 用 Manacher
11	盛最多水的容器	O(n) / O(1)	面积由短板决定，移动长板只会更小 → 只移短板
15	三数之和	O(n²) / O(1)	排序后固定一个数，剩余两数对撞；跳过重复值
16	最接近的三数之和	O(n²) / O(1)	与 15 同构，维护 `
18	四数之和	O(n³) / O(1)	两层固定 + 对撞；去重逻辑与 15 相同
26	删除有序数组重复项	O(n) / O(1)	读写双指针，写指针只在"新值"时前进
27	移除元素	O(n) / O(1)	同上；返回值是新长度，尾部内容无意义
28	实现 strStr	O(n+m) / O(m)	KMP 前缀函数，避免回退；暴力是 O(nm)
30	串联所有单词子串	O(n·L) / O(L)	按单词长度分组，每组内滑动窗口
75	颜色分类	O(n) / O(1)	荷兰国旗三路划分：一次遍历分三段
76	最小覆盖子串	O(n) / O(Σ)	窗口内维护"还差几个字符"，欠账=0 时收缩

2. 二分（精讲 J02）

题	名称	时间 / 空间	一句话洞察
4	两个正序数组中位数	O(log(m+n)) / O(1)	在短数组上二分划分点，保证左右两半元素数相等
29	两数相除	O(log n) / O(1)	用"减法翻倍"代替试商；注意 −2³¹ 溢出
33	搜索旋转排序数组	O(log n) / O(1)	先判 `mid` 落在哪半有序，再决定收缩方向
34	找首末位置	O(log n) / O(1)	两次二分：lower_bound 与 upper_bound
35	搜索插入位置	O(log n) / O(1)	就是求 lower_bound；找不到时返回插入点
50	Pow(x,n)	O(log n) / O(1)	快速幂；负指数取倒数
69	x 的平方根	O(log x) / O(1)	二分答案：最大 x 使 x² ≤ n
74	搜索二维矩阵	O(log(mn)) / O(1)	行列均有序 → 可视为一维有序数组
81	旋转排序数组 II	O(log n) 平均 / O(1)	有重复值时无法判有序 → 收缩边界退化为 O(n)

3. 链表（精讲 J03）

题	名称	时间 / 空间	一句话洞察
2	两数相加	O(max(m,n)) / O(1)	同时走两链 + 进位；注意长度不等与最后进位
19	删除倒数第 N	O(n) / O(1)	快指针先走 N 步，再同步走；用虚拟头免特判
21	合并两个有序链表	O(m+n) / O(1)	归并；哨兵节点简化头节点处理
23	合并 K 个有序链表	O(N log k) / O(k)	小顶堆存每个链头；或两两分治
24	两两交换节点	O(n) / O(1)	三指针：prev / a / b，每轮换完推进两步
25	K 个一组翻转	O(n) / O(1)	先数够 K 个再翻；不足 K 个保持原样
61	旋转链表	O(n) / O(1)	连成环，长度 L 后断在 `L - k%L` 处
82	删除重复元素 II	O(n) / O(1)	虚拟头 + 跳过整段同值；保留只出现一次的
83	删除重复元素	O(n) / O(1)	相邻比较，重复就跳过（保留一个）
86	分隔链表	O(n) / O(1)	两条子链（<x / ≥x）拼接，避免原地插入
92	反转链表 II	O(n) / O(1)	虚拟头 + 四指针：前驱、区间首、区间尾、后继

4. 回溯与搜索（精讲 J04）

题	名称	时间 / 空间	一句话洞察
17	电话号码字母组合	O(4ⁿ) / O(n)	每个数字的候选集做笛卡尔积
22	括号生成	O(4ⁿ/√n) / O(n)	只要"左括号已用 < n 且左 ≥ 右"就合法
37	解数独	O(9^81) 最坏 / O(1)	行/列/宫三个位掩码，选候选最少的格子先填
39	组合总和（可重复）	O(2ⁿ) / O(n)	传 `start` 保证不回头选，允许重复取自身
40	组合总和 II	O(2ⁿ) / O(n)	先排序，同层跳过相同值避免重复组合
46	全排列	O(n!) / O(n)	交换法或 used 数组；撤销现场是关键
47	全排列 II	O(n!·n) / O(n)	排序 + "同层相同值只用第一个"
51	N 皇后	O(n!) / O(n)	三个方向集合（列/主对角/副对角）用位掩码判断
52	N 皇后 II	O(n!) / O(1)	同 51，只计数不记录棋盘
77	组合	O(C(n,k)) / O(k)	选够 k 个即收集；剪枝：剩余不够就返回
78	子集	O(2ⁿ) / O(n)	每个元素"选/不选"两分支
79	单词搜索	O(m·n·4^L) / O(L)	网格 DFS + 回溯标记；起点逐个尝试
90	子集 II	O(2ⁿ) / O(n)	排序 + 同层去重
93	复原 IP 地址	O(3⁴) / O(1)	每段 1–3 位、≤255、无前导 0；4 段用完且到末尾才算解

5. 动态规划（精讲 J05）

题	名称	时间 / 空间	一句话洞察
10	正则匹配	O(mn) / O(mn)	`*` 分"匹配 0 次"与"匹配多次"两支
44	通配符匹配	O(mn) / O(mn)	`*` 可匹配任意串；`?` 匹配单字符
53	最大子数组和	O(n) / O(1)	Kadane：`cur = max(x, cur+x)`，负数即重开
62	不同路径	O(mn) / O(n)	`dp[j] += dp[j-1]` 一维滚动
63	不同路径 II	O(mn) / O(n)	障碍处 dp=0；初始化也要跳过障碍
64	最小路径和	O(mn) / O(n)	只能从上方或左侧来，取 min
70	爬楼梯	O(n) / O(1)	斐波那契；滚动两个变量即可
72	编辑距离	O(mn) / O(mn)	三种操作取 min；初始化为 i / j
87	扰乱字符串	O(n³) / O(n²)	区间 DP + 记忆化；枚举分割点两两组合
91	解码方法	O(n) / O(1)	当前位可单独解（1–9）或与前者组合（10–26）
97	交错字符串	O(mn) / O(n)	`dp[i][j]` 表示 s1 前 i + s2 前 j 能否拼出 s3 前 i+j

6. 栈与单调栈（精讲 J06）

题	名称	时间 / 空间	一句话洞察
20	有效括号	O(n) / O(n)	栈顶匹配；结束栈必须为空
32	最长有效括号	O(n) / O(n)	栈存下标（含一个哨兵 −1），弹出后算长度
42	接雨水	O(n) / O(n)	单调递减栈；或双指针维护左右最大高度
71	简化路径	O(n) / O(n)	按 `/` 切分，`..` 弹栈，`.` 与空段忽略
84	柱状图最大矩形	O(n) / O(n)	单调递增栈；哨兵 0 保证全部弹出
85	最大矩形	O(mn) / O(n)	逐行累加柱高，每行跑一次 84

7. 其余题（无独立精讲，索引在此）

题	名称	模式	时间 / 空间
1	两数之和	哈希	O(n) / O(n)
6	Z 字形变换	模拟	O(n) / O(n)
7	整数反转	逐位 + 溢出检查	O(log n) / O(1)
8	字符串转整数	状态机	O(n) / O(1)
9	回文数	反转一半比较	O(log n) / O(1)
12	整数转罗马	查表贪心	O(1) / O(1)
13	罗马转整数	相邻比较	O(n) / O(1)
14	最长公共前缀	纵向扫描	O(S) / O(1)
31	下一个排列	从右找升序 + 反转	O(n) / O(1)
36	有效数独	位掩码/哈希	O(1) / O(1)
38	外观数列	模拟报数	O(L) / O(L)
41	缺失的第一个正数	原地哈希（值→下标）	O(n) / O(1)
43	字符串相乘	竖式模拟	O(mn) / O(m+n)
45	跳跃游戏 II	贪心（层边界）	O(n) / O(1)
48	旋转图像	转置 + 翻转	O(n²) / O(1)
49	字母异位词分组	排序/计数作 key	O(n·k log k) / O(nk)
54	螺旋矩阵	四边界模拟	O(mn) / O(1)
55	跳跃游戏	维护最远可达	O(n) / O(1)
56	合并区间	排序后合并	O(n log n) / O(n)
57	插入区间	三段式	O(n) / O(n)
58	最后一个单词长度	反向扫描	O(n) / O(1)
59	螺旋矩阵 II	模拟填充	O(n²) / O(n²)
60	排列序列	康托/递归选数	O(n²) / O(n)
65	有效数字	状态机（DFA）	O(n) / O(1)
66	加一	进位模拟	O(n) / O(1)
67	二进制求和	逐位进位	O(n) / O(n)
68	文本左右对齐	贪心分行 + 空格分配	O(n) / O(n)
73	矩阵置零	用首行首列做标记	O(mn) / O(1)
80	删除重复项 II	三指针（保留两次）	O(n) / O(1)
88	合并两个有序数组	从后往前（避免覆盖）	O(m+n) / O(1)
89	格雷编码	`i ^ (i>>1)`	O(2ⁿ) / O(1)
94	二叉树中序遍历	栈/递归	O(n) / O(h)
95	不同的 BST II	递归分治构造	O(Cₙ) / O(n)
96	不同的 BST	卡特兰数	O(n²) / O(n)
98	验证 BST	中序递增 / 上下界	O(n) / O(h)
99	恢复 BST	中序找逆序对	O(n) / O(h)
100	相同的树	递归比较	O(n) / O(h)

8. 按模式回查（做不出题时先看这里）

题目特征	模式	精讲
有序数组 + 找目标/边界	二分	J02
连续子数组 + 窗口内条件	滑动窗口	J01
两数/三数/面积 + 排序	对撞双指针	J01
链表 + 倒数/中间/环形	快慢指针	J03
枚举所有"组合/排列/方案"	回溯	J04
求"最少/最大/方案数" + 有重叠子问题	DP	J05
"下一个更大/更小元素"	单调栈	J06
括号/表达式/路径解析	栈	J06
去重/计数/两数配对	哈希	B04
前 K 个/第 K 大	堆	B05
前缀匹配/自动补全	Trie	B06
动态连通性	并查集	B07

9. 空壳卡与重复卡的处理（本索引的登记说明）

情况	卡	处理
只有题干无答案（25 张）	#11/20/24/27/32/38/42/43/51/53/56/58/61/62/71/79/82/91/97/100 等	在 J 系列补写，标 `E-S03-111`~`E-S03-126`；本索引只给模式与复杂度
同题重复（4 组）	#4/#5/#6/#7 各有一张薄卡	薄卡标 `duplicate_ref`，内容并入富卡
笔记类卡（无题号）	A-2483/A-2574 等	进 `gaps.md` 的"卡外内容"清单

10. 下一篇

S03-J01 · 双指针与滑动窗口

从索引进入精讲。第一篇讲"用两个指针代替双层循环"的成立条件：为什么右指针只进不退、左指针什么时候收缩，并用暴力 O(n²) 与滑窗 O(n) 的实测耗时说明差距。

本篇属于系列《S03 · 数据结构与算法》，是基础层附录。旧文来源：104 张题解卡（12,119 点位）；每条一行均可回到 coverage.csv 的 source_id 核对。