双指针：具体场景与手把手推演¶
覆盖：三种双指针的具体场景、算法 vs SQL 工程差异、逐步推演、代码模板与刷题清单 适用：单独搞懂双指针，不混谈滑动窗口和数组历史 前置：知道数组和下标即可；细节见 数组
← 返回 总览 | 相关 数组 | 7 天冲刺 Day 1
读前 30 秒：双指针到底是什么？¶
在数组、字符串或链表上放 两个下标（常叫 left/right 或 slow/fast），按固定规则一起移动。
它解决的一类问题：本来要两重循环试所有组合 → O(n²)，利用 有序、单调、或原地写入 等性质，每走一步 排除一大批不可能 → O(n)。
暴力：试每一对、每一个起点终点 → n²
双指针：两个指头有方向地动 → n
本文按 三种姿势 展开，每种都配 具体业务场景 + 纸上推演 + 对应 LeetCode。
一、三种双指针，一张表先分清¶
| 类型 | 两个指针怎么放 | 怎么动 | 典型业务 | 代表题 |
|---|---|---|---|---|
| 对撞指针 | 一左一右 | 向中间靠 | 对账、回文、盛水 | LC 167, 11, 125 |
| 快慢指针 | 同侧，一前一后 | 都往右，快的多走 | 去重、压缩、链表环 | LC 26, 283, 141 |
| 同向 / 逆向双指针 | 各扫一个有序序列 | 谁小/谁大谁先动 | 归并日志、MERGE JOIN | LC 88, 21, 977 |
和滑动窗口的区别（避免混）：滑动窗口强调 框住连续一段 并统计窗口内状态；双指针更宽，不一定在维护「连续区间长度」。详见 数组 § 滑动窗口。
二、算法思维 vs 工程实践（数据开发为什么「日常感觉不到」）¶
做计费、对账、数仓的同学常问：我天天写 SQL JOIN，从没写过双指针，这玩意到底有啥用？
下面分四点拆开——这也是 面试算法 和 线上 SQL 之间的那层窗户纸。
2.1 双指针是为了更快「找到某个元素」吗？¶
不完全是。
双指针的核心价值是：在 有序或单调 的结构上，用 O(n) 解决原本要 O(n²) 的嵌套循环问题，从而做 比较、匹配、去重、合并 这类结构性操作。
| 典型场景 | 在干什么 | 是不是「查找某一个元素」 |
|---|---|---|
| 有序数组两数之和 | 找一对和为 target | 否，是 配对 |
| 合并两个有序数组 | 归并成一条 | 否，是 合并 |
| 链表判环 | 快慢相遇 | 否，是 结构检测 |
| 原地去重 | 压缩有效区 | 否，是 原地写 |
所以：别把它理解成「二分那种找一个下标」，而是 两个游标协同扫一遍，省掉内层循环。
2.2 为什么计费 / 数据开发里「好像没见过」？¶
因为日常工作在 SQL 引擎之上。SQL 是 声明式 的：你写「要什么」，优化器决定用 Hash Join、Nested Loop 还是 Sort-Merge Join。
Sort-Merge Join 的底层，就是两个有序扫描指针一左一右对齐匹配——逻辑上就是双指针（或等价的双向遍历），只是：
- 发生在 数据库进程里
- 由 C++/Java 引擎 实现
- 你在 SQL 里 看不见
left++、right--
-- 示意：两表按 join key 排序后做 Merge Join
SELECT *
FROM A
JOIN B ON A.amount = B.amount;
-- 若优化器选 Merge Join：先排序，再双路扫描对齐 amount
你没写过双指针，不等于线上没用双指针思想——是引擎替你做了。
2.3 计费对账为什么多半「SQL 关联 + 差异条件」就够？¶
计费场景常见特点：
| 特点 | 带来的做法 |
|---|---|
| 数据量 TB 级 | 必须落在 DB / 湖仓，不能全拉进 Python 内存 |
| 有 交易号、订单号、批次号 等主键 | JOIN ON id 或 FULL OUTER JOIN 找丢单、重复 |
| 差异类型多是 丢单、重复、金额不等、时间窗偏移 | WHERE a.id IS NULL OR a.amt <> b.amt 即可 |
这类问题 天然有唯一键或业务键，引擎用 哈希或排序合并 做关联，比你在应用层手写双指针合适得多。
而 LeetCode 式双指针常假设：
- 数据在 内存（
int[]、链表节点） - 没有 稳定唯一键，只能按 排序后的位置 / 值 配对
- 数据量 小到 一台机器装得下
所以：日常批量对账用 SQL 是对的；双指针题考的是「没有数据库替你干时，你怎么 O(n) 扫」。
2.4 什么时候双指针会比 SQL 更合适？¶
当你 离开声明式引擎，或问题 不适合用主键 JOIN 时，双指针会很好用。
真实排错场景（一次性、小数据）：
银行 CSV 流水 + 内部计费导出 CSV，两边都没有唯一交易号，只能按 金额 + 时间 近似对齐。金额已排序，怀疑有「错位配对」导致差额 700 元。
用 SQL 也能做，但往往要：
- 建临时表、导入
- 窗口函数
LAG/LEAD比相邻行 - 处理排序、去重、边界
用 Python / Java 读两个排序后的列表，双指针扫金额差：
- 逻辑直观（和本文 §三 场景 1 同一套）
- 代码短，适合 adhoc 排查
- 不必为几百行 CSV 搭一套 SQL 管道
| 维度 | SQL 关联（日常对账） | 双指针（内存 / 脚本） |
|---|---|---|
| 适用数据量 | 大（TB 级） | 小（内存能放下） |
| 执行位置 | DB / Spark / Flink 引擎 | 应用进程、Notebook、脚本 |
| 是否依赖唯一键 | 通常 需要，否则 SQL 很绕 | 可按 排序 + 位置 比较 |
| 你是否「看见」算法 | 优化器黑盒 | 自己写循环，完全可见 |
| 典型计费场景 | 日批对账、差异报表 | CSV 排错、Kafka 双流实时对齐、面试题 |
一句话：没遇到过，是因为 引擎替你做掉了，或 场景有主键不需要它；一旦在内存里处理两个有序序列，双指针是随手可用的工具。
三、对撞指针：从两端往中间夹¶
场景 1：财务对账——两笔流水之和等于差额¶
业务背景
出纳要对账：系统显示差额 700 元，怀疑是两笔 已按金额排序 的流水一出一进配错了。
流水（已排序）: [100, 300, 500, 800, 1200]
要找：两笔 a + b = 700
暴力怎么做
两重循环，试 (100,300)、(100,500)… 共约 n²/2 对。10 万条流水就崩。
双指针怎么做
left → 最小 right → 最大
[100, 300, 500, 800, 1200]
↑ ↑
| 步 | left | right | 和 | 动作 | 排除了什么 |
|---|---|---|---|---|---|
| 1 | 100 | 1200 | 1300 | 太大 → right-- | 100 配 1200、800… 都不可能（和都更大） |
| 2 | 100 | 800 | 900 | 太大 → right-- | |
| 3 | 100 | 500 | 600 | 太小 → left++ | 300 配 800、500… 要试 |
| 4 | 300 | 500 | 700 | 找到 |
规则（背三句）
- 和 太小 →
left++（换更大的左边） - 和 太大 →
right--（换更小的右边） - 和 相等 → 结束
对应题目：167. 两数之和 II
前提：数据 有序。无序用哈希表（LC 1）。
场景 2：盛最多水的容器（LC 11）¶
对应题目：11. 盛最多水的容器
文档里曾用「两仓库货位」作类比；若类比干扰理解，直接记「两根竖线夹水」 即可。下面从原题讲起。
题目在画什么？¶
有一排 竖线，第 i 根高度是 height[i]。选 两根 当左右边界，中间可以「装水」：
高度
8 | █
6 | █ █ █
4 | █ █ █ █
2 | █ █ █ █ █
+---+---+---+---+---+---→ 下标
0 1 2 3 4 5 6 7
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
选下标 left=1（高 8）和 right=6（高 8）：
█ █
█ █
█ ~ ~ ~ ~ ~ █ ← 水的高度 = 较矮那根 = 8
█ ~ ~ ~ ~ ~ █
█ ~ ~ ~ ~ ~ █
容量公式：
容量 = 宽度 × min(左高, 右高)
= (right - left) × min(height[left], height[right])
- 宽度：两根线之间的水平距离
- 高度：水装不满较高的那根，会溢出，所以取 较矮 的那侧
上例：宽度 = 6−1 = 5，高度 = min(8,8) = 8 → 容量 = 40。
暴力在干什么？¶
任选两个下标 (i, j)，算 min(h[i], h[j]) × (j - i)，取最大。
大约要试 n²/2 对，n = 10⁵ 时会超时。
双指针怎么做？¶
left 从最左，right 从最右，算当前容量，然后 只移动较矮的那一侧：
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
if (height[left] < height[right]) left++;
else right--;
为什么动「较矮」的那边？
left 矮，right 高
矮| |高
| ~~~~~ |
+--------------+
←── 宽度 W ──→
- 若 动较高的 right（往左缩）：宽度 一定变小，高度仍受 矮的 left 限制 → 容量 只会更小或不变，不可能变大。
- 若 动较矮的 left（往右移）：宽度变小，但 left 可能变高 → 高度有机会变大，容量 还有可能变大。
所以：只有动矮边才值得继续试；动高边是在白试。
手把手推演（前几步）¶
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]，初始 left=0, right=8：
| 步 | left | right | 高左 | 高右 | 宽 | 容量 = min×宽 | 动谁 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 1 | 7 | 8 | 1×8=8 | left（1<7） |
| 2 | 1 | 8 | 8 | 7 | 7 | 7×7=49 | right（8>7） |
| 3 | 1 | 7 | 8 | 3 | 6 | 3×6=18 | right |
| … | … | … | … | … | … | … | 每次动较矮端 |
全程维护 ans 的最大值；本题最优容量为 49。
不必手算全程，记住：每次 O(1) 算面积，只动矮边，两指针各最多走 n 步 → O(n)。
和「两数之和 II」对撞指针的异同¶
| 两数之和 II | 盛最多水的容器 | |
|---|---|---|
| 指针 | 两端往中间 | 两端往中间 |
| 比较什么 | sum 和 target |
容量，取最大 |
| 移动规则 | 和太小动 left，太大动 right | 永远动较矮的那边 |
| 目标 | 找到等于 target | 扫描过程中维护 最大值 |
都是 对撞双指针，移动规则不同：一个看「和与 target」，一个看「哪边是瓶颈」。
业务联想：「宽 × 矮」在真实系统里长什么样？¶
LC 11 是 在一条线上选两个点使面积最大；业务里很少有人手写 left++/right-- 去算带宽，但 「两个边界之间能承载多少 = 宽度 × 较弱那侧的上限」 极其常见——这就是流水线里的 瓶颈（bottleneck） 思想。
下面每个例子都按同一套模板写：
容量/吞吐 ≈ 宽度（时间、距离、区间长度）× min(左端能力, 右端能力)
↑
「较矮的那根线」
例子 1：跨机房 / 跨区数据传输（带宽）¶
场景
要把对象存储里的大文件从北京机房传到上海机房，中间走专线。
两端网卡、专线入口的 额定带宽不同。
北京出口上限: 10 Gbps ←── 较「高」
上海入口上限: 5 Gbps ←── 较「矮」 → 整条链路瓶颈 5 Gbps
传输持续: 2 小时 ←── 「宽度」
怎么算
实际可传数据量 ≈ 5 Gbps × 2h（取 min(10, 5)，不是 10）。
你加再宽的北京出口，在上海入口仍是 5 Gbps 之前，总传输量不会变——就像 动「较高的 right」无助于增大盛水量。
和题目的对应
| LC 11 | 带宽场景 |
|---|---|
height[i] |
某节点/链路段的带宽上限 |
right - left |
传输持续时长、或路径上覆盖的跳数 |
min(左高, 右高) |
端到端有效带宽（瓶颈段） |
| 动较矮边 | 扩容时先找 最窄的那一段 加带宽，而不是盲目加宽已经够宽的一端 |
例子 2：CDN / 用户下载（双段链路）¶
场景
用户从 CDN 边缘节点拉取视频：
用户 ↔ 边缘 一段，边缘 ↔ 源站 一段。
用户家宽: 100 Mbps
边缘↔源站: 20 Mbps ←── 瓶颈
播放时长: 1 小时
用户感知到的稳定下载速度 ≈ min(100, 20) = 20 Mbps，不会因为是 100M 宽带就变成 100M 下载。
「水的高度」由 较矮的那段链路 决定；「宽度」可以是时长或文件大小对应的传输窗口。
运维在干什么
排障时看 min(各段)；优化时 先抬矮边（加回源带宽、换更近源站），而不是只给用户升家庭带宽。
例子 3：仓储通道堆货（和「货位高度」最贴近的类比）¶
场景
仓库里两条平行货架之间有一条通道，要在通道上方做 统高堆货（例如托盘层）。
通道 左端 已有货堆高 3m，右端 已有货堆高 5m，通道水平长度 20m。
左端堆高: 3m ←── 较矮 → 通道内能堆的统一高度 ≤ 3m
右端堆高: 5m
通道长度: 20m ←── 宽度
可堆体积（简化） ≈ 3m × 20m × 通道宽——再高会被左端挡住。
要想多装货：要么 加高左端能力（挪走左侧低位货），要么 缩短通道（缩小宽度）但换更高的左端——和「动矮边、看能不能遇到更高的线」是同一类权衡。
例子 4：流水线双工位产能（制造业 / 计费批处理）¶
场景
一条流水线两个环节：
- 环节 A（上游）：最多 100 条/分钟
- 环节 B（下游）：最多 60 条/分钟
连续跑 8 小时。
有效产出 ≈ min(100, 60) × 8h = 60 条/分钟 × 8h
↑ 瓶颈工位
整条线 再快也超不过 60——多雇人加 A 的产能，B 不动，总产量不变。
Lean 里叫 瓶颈工序；和 min(左高, 右高) 完全一致。
数据开发里的同类
Spark 作业里 Shuffle 写磁盘 500MB/s、读磁盘 200MB/s，Stage 间有效吞吐按 200 算；优化先找 最慢的那一段（慢磁盘、小 partition、热点 key）。
例子 5：主从库同步 / 双端写入上限¶
场景
MySQL 主库写入峰值 5000 TPS，从库回放 binlog 能力 3000 TPS，高峰持续 30 分钟。
可安全同步的事务量 ≈ 3000 TPS × 30min
↑ 从库是「较矮边」
主库再飙到 8000 TPS，从库仍 3000，积压只会涨——除非 抬高从库（动矮边） 或 拉长时间窗口换别的策略，而不是只扩主库。
例子 6：广告 / 计费——双端配额与填充率¶
场景
一次投放同时在 媒体 A 和 媒体 B 上跑 7 天（宽度 = 7 天）。
- A 的库存/填充能力：日均 100 万次曝光
- B 的填充能力：日均 40 万次
若策略要求 两端同步放量、按 min 对齐（简化模型）：
有效日均曝光 ≈ min(100万, 40万) = 40万
7 天总量 ≈ 40万 × 7
只加 A 的预算，B 仍 40 万，总有效曝光不变——要先抬 B 的 fill rate 或换量更大的 B。
例子 7：API 网关双端限流¶
场景
- 客户端合同：1000 QPS
- 下游核心服务：200 QPS
- 促销持续 1 小时
实际可持续调用 ≈ min(1000, 200) = 200 QPS
总可处理 ≈ 200 × 3600
网关再放宽客户端配额，核心仍是 200，只会排队/超时——扩容应 先动矮边（核心或缓存）。
和 LC 11 双指针算法 的关系（别混）¶
| 层面 | 业务里 | LC 11 题里 |
|---|---|---|
公式 min × 宽 |
带宽、产能、限流、堆货高度——天天见 | 竖线间盛水面积 |
| 双指针 O(n) | 一般 不会 手写去扫「哪两个机房配对最大」 | 在 高度数组 上找最优区间 |
| 动矮边 的直觉 | 优化瓶颈段、先扩最窄环 | 证明双指针不漏最优解 |
业务上记住 瓶颈在 min 那一侧 就够应付 90% 的对话；面试再记 竖线夹水 + 动矮边 的代码。
口诀：夹水，容量 = 宽 × 矮；动矮边，别动高边。业务里：先找 min 那段，再谈加宽。
场景 3：验证码 / 基因序列——是不是回文¶
业务背景
用户输入 A man, a plan, a canal: Panama，系统要去掉空格和标点，判断是否回文（正反读一样）。
双指针
left 从头，right 从尾，跳过非字母数字，比较 s[left] 和 s[right]，不等则否，相等则 left++、right--。
清理后: a m a n a p l a n a c a n a l p a n a m a
↑ ↑
left right
对应题目：125. 验证回文串
业务同类：对称结构校验、DNA 回文片段、回文 ID 规则。
场景 4：风控——三笔交易之和为可疑金额¶
业务背景
sorted 交易金额，找 三笔 之和 = 0（或某阈值），上报可疑。
做法
固定最左边一笔 i，在 [i+1, n-1] 上用 对撞指针 找两数之和 = -nums[i]。
外层 i 从 0 到 n-3，内层对撞 → 总体 O(n²)，比 O(n³) 暴力三省一层。
对应题目：15. 三数之和
对撞指针小结¶
| 什么时候用 | 信号词 |
|---|---|
| 数组 已排序 | sorted、升序、两数之和 |
| 两端 向中间逼近 | 盛水、回文 |
| 固定一端 + 内层对撞 | 三数之和 |
四、快慢指针：同侧，快的探路、慢的落笔¶
场景 5：ETL 去重——排序后的用户 ID 流¶
业务背景
上游 Kafka topic 里的 userId 已排序，写入下游前要去重，且 尽量原地写、少占内存。
输入: [1001, 1001, 1002, 1002, 1003]
角色
slow：有效区最后一个位置（「打包员」）fast：逐个读新 ID（「质检员」）
步 1: [1001, 1001, ...] slow=0, fast=1 → 相同，fast++
步 2: [1001, 1002, ...] 不同 → slow++，写 nums[slow]=nums[fast]
...
结果: [1001, 1002, 1003] 长度 slow+1 = 3
对应题目：26. 删除有序数组中的重复项
场景 6：日志清洗——把无效记录挪到后面（移动零）¶
业务背景
一批状态码里，要把 0（失败/无效） 都挪到数组末尾，保持非零元素的相对顺序，原地、O(1) 额外空间。
输入: [0, 1, 0, 3, 12]
fast 扫，见到非零就交给 slow 写
输出: [1, 3, 12, 0, 0]
和去重的同一套框架：fast 探路，slow 写「要保留的」。
对应题目：283. 移动零
业务同类：compaction、过滤后 compact 内存池、稀疏数组整理。
场景 7：依赖有没有环——链表 / 任务引用¶
业务背景
任务 A → B → C → B，形成环，调度器会死循环。链表 不知道长度，不能先数一遍再判环。
Floyd 判圈（龟兔赛跑）
slow每次走 1 步fast每次走 2 步- 若有环，fast 一定会在环里追上 slow
A → B → C
↑ ↓
E ← D
slow 和 fast 进环后，fast 像操场跑圈多跑，必相遇
对应题目：141. 环形链表
业务同类：循环依赖检测、引用环、GC 可达性（思想类似）。
场景 8：大文件切半——找链表中点¶
业务背景
单链表要 分片 给两个 worker，需要找 中点 切开，且只能扫一遍。
做法
slow 走 1 步，fast 走 2 步；fast 到尾时 slow 在中点。
对应题目：876. 链表的中间结点
快慢指针小结¶
| 什么时候用 | 信号词 |
|---|---|
| 原地 修改数组 | 去重、移动零、过滤 |
| 链表 不知长度 | 环、中点 |
| 写指针 + 读指针 | 单遍扫描、O(1) 空间 |
五、同向 / 逆向双指针：两个有序序列归并¶
场景 9：合并两个按时间排序的日志流¶
业务背景
服务 A、服务 B 各产出 按 timestamp 排序 的日志，要合成一条时间线给检索用。
A: [1:01, 1:05, 1:09]
B: [1:03, 1:07, 1:08]
同向双指针
i 指 A，j 指 B，每次取 较小 timestamp 的那条写入结果，对应指针 +1。
结果: [1:01, 1:03, 1:05, 1:07, 1:08, 1:09]
对应题目：977. 有序数组的平方（负数平方后两端大、中间小，也可双指针）、21. 合并两个有序链表
场景 10：数据库 MERGE JOIN¶
业务背景
表 R、S 在 join key 上都已排序（或有有序索引）。DB 不用嵌套循环 O(n×m)，而是两个扫描指针：
key 相等 → 输出匹配行；R 小 → R 指针前进；S 小 → S 指针前进。
R: [10, 20, 30, 40]
S: [15, 20, 20, 35]
匹配: 20-20, 20-20
这就是归并的双指针，和合并两个有序数组 同一套逻辑。
对应题目：88. 合并两个有序数组
场景 11：合并到 A 数组末尾（逆向填，避免覆盖）¶
业务背景
A 末尾有空位，要把 B 合并进 A，不能另开一个大数组。若从前往后填，会把 A 里还没处理的数盖住。
逆向双指针
i 指 A 有效区最后，j 指 B 最后，k 指 A 物理最后；谁大写谁到 k，从后往前填。
A: [1, 3, 5, _, _, _] m=3
B: [2, 4, 6] n=3
从尾部填: 6, 5, 4, 3, 2, 1
对应题目：88. 合并两个有序数组
业务同类：Git 合并两个有序 commit 线、版本 diff 归并。
同向 / 逆向小结¶
| 什么时候用 | 信号词 |
|---|---|
| 两个有序 序列 | merge、归并、JOIN |
| 结果写进 其中一个数组尾部 | 逆向双指针 |
| 单链表合并 | 每次取较小节点 |
六、场景 → 题目速查表¶
| # | 业务场景 | 双指针类型 | LeetCode |
|---|---|---|---|
| 1 | 两笔 sorted 流水之和 = 差额 | 对撞 | 167 |
| 2 | 两边界之间最大容量/效益 | 对撞 | 11 |
| 3 | 回文验证码 / 对称串 | 对撞 | 125 |
| 4 | 三笔交易之和可疑 | 对撞 + 固定一端 | 15 |
| 5 | sorted ID 流去重 | 快慢 | 26 |
| 6 | 无效记录挪末尾 | 快慢 | 283 |
| 7 | 任务/引用环 | 快慢 | 141 |
| 8 | 链表找中点分片 | 快慢 | 876 |
| 9 | 两路 sorted 日志归并 | 同向 | 21 |
| 10 | 有序索引 JOIN | 同向 | （思想同 88） |
| 11 | 原地合并进 A 尾部 | 逆向 | 88 |
七、拿到题怎么判断用哪种？¶
数组/字符串/链表题
│
├─ 两个 **有序** 序列要合成一个？
│ └─ 同向双指针（或逆向填，见 [§五 场景 11](#场景-11合并到-a-数组末尾逆向填避免覆盖)）
│
├─ **已排序** + 找两个/三个数和？
│ └─ 对撞（三数之和：固定一端 + 内层对撞）
│
├─ **两端** 向中间、回文、盛水？
│ └─ 对撞
│
├─ **原地** 去重 / 过滤 / 挪零？
│ └─ 快慢
│
├─ 链表 + 环 / 中点 / 不知长度？
│ └─ 快慢
│
└─ 无序 + 任意两数之和？
└─ 哈希表（LC 1），不是双指针
八、代码模板（Java）¶
// ========== 1. 对撞：有序两数之和 ==========
public int[] twoSumSorted(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left + 1, right + 1};
if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}
// ========== 2. 对撞：盛最多水的容器 ==========
public int maxArea(int[] h) {
int left = 0, right = h.length - 1, ans = 0;
while (left < right) {
ans = Math.max(ans, Math.min(h[left], h[right]) * (right - left));
if (h[left] < h[right]) left++;
else right--;
}
return ans;
}
// ========== 3. 快慢：原地去重 ==========
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
// ========== 4. 快慢：移动零 ==========
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
int tmp = nums[slow];
nums[slow++] = nums[fast];
nums[fast] = tmp;
}
}
}
// ========== 5. 快慢：链表环 ==========
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
// ========== 6. 逆向：合并两个有序数组 ==========
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
while (j >= 0) nums1[k--] = nums2[j--];
}
九、必刷题目¶
| 优先级 | 题目 | 类型 | 场景 |
|---|---|---|---|
| ⭐⭐⭐ | 167 两数之和 II | 对撞 | 对账 |
| ⭐⭐⭐ | 15 三数之和 | 对撞 | 风控 |
| ⭐⭐⭐ | 11 盛最多水的容器 | 对撞 | 边界优化 |
| ⭐⭐⭐ | 26 删除有序重复项 | 快慢 | ETL 去重 |
| ⭐⭐⭐ | 88 合并两个有序数组 | 逆向 | 日志/MERGE JOIN |
| ⭐⭐ | 283 移动零 | 快慢 | 原地过滤 |
| ⭐⭐ | 125 验证回文串 | 对撞 | 校验 |
| ⭐⭐ | 141 环形链表 | 快慢 | 环检测 |
| ⭐⭐ | 21 合并两个有序链表 | 同向 | 双路归并 |
| ⭐⭐⭐ | 42 接雨水 | 对撞/双指针 | 进阶 |
十、小结¶
| 类型 | 一句话 | 业务联想 |
|---|---|---|
| 对撞 | 有序数组两端往中间夹，和太大动右、太小动左 | 对账、回文、盛水 |
| 快慢 | 同侧，快探路慢写入；链表快走两步 | 去重、挪零、判环、中点 |
| 同向/逆向 | 两个 sorted 序列，取小归并；原地合并则逆向填 | 日志归并、MERGE JOIN |
| 工程侧 | SQL Merge Join 底层即双路扫描；日常对账用 JOIN，排错 CSV 用脚本双指针 | 见 §二 |
练习建议：每个类型至少 手写推演 一题（167 / 26 / 88），再在 LeetCode 各刷 2 题巩固。