数组：从内存布局到滑动窗口¶
覆盖：数组的历史渊源、滑动窗口、前缀和；双指针见 双指针专题 适用：Day 1 专题深读，或面试前快速回顾数组相关技巧 方法：5W1H（为什么学、学什么、何时用、在哪用、谁在用、怎么用）
← 返回 数据结构与算法总览 | 双指针专题 | 树专题 | 7 天冲刺 Day 1
读前须知：这篇在讲什么？¶
如果你之前「看了表、看了结论，还是懵」，通常卡在三个地方：
- 数组：听起来像
int[]，和历史里的「发明」有什么关系？ - 双指针：两个变量
left/right在干嘛？为什么能少算很多遍？ - 滑动窗口：和 TCP、限流里的「窗口」是一回事吗？和双指针有什么区别？
下面按 先建立直觉 → 再讲历史 → 再手把手推演一道题 → 最后对照业务 的顺序写。
你可以先只看 §0 直觉 和 §二、§三 里的「手把手推演」，回头再读历史。
§0 先用生活例子建立直觉（不看代码也能懂）¶
0.1 数组是什么？¶
把内存想成 一排带门牌号的储物柜：
门牌号: 1000 1001 1002 1003 1004
┌────┬────┬────┬────┬────┐
│ 85 │ 92 │ 78 │ 96 │ 88 │ ← 五个学生成绩
└────┴────┴────┴────┴────┘
↑
第 0 个（下标从 0 开始）
- 数组 = 占连续多格柜子，存同一类东西（都是成绩）
- 下标
i= 第几个柜子，从 0 数起 arr[i]= 直接开门牌起始地址 + i，所以是 O(1)，不用从第一格挨个找
没有数组时：你要写 score0, score1, ... score99，没法写 for (i=0; i<100; i++)，一百个变量没法批量算平均分。
0.2 双指针是什么？（一句话）¶
在数组（或字符串）上放两个下标，按规则一起移动，每走一步就排除一大批「不可能」的情况，从而不用两重循环。
两种常见姿势：
| 类型 | 两个指针怎么动 | 生活类比 |
|---|---|---|
| 对撞指针 | 一个在左、一个在右，往中间靠 | 两个人从操场两端往中间走，找「身高之和 = 某数」的配对 |
| 快慢指针 | 都在左边，快的往前探，慢的负责「写结果」 | 质检员（快）往前看，打包员（慢）只把合格品放进箱子 |
0.3 滑动窗口是什么？（一句话）¶
只关心「连续的一段」（连续子数组/子串），用
left和right框住这段，右边界扩大时往里加，不满足条件时从左缩出去。
字符串: a b c a b c b b
[———] ← 窗口里是 "bca"，无重复，长度 3
left right
和双指针的关系：滑动窗口往往也是对撞/同向双指针的一种用法，但题目里强调「连续区间」「窗口内统计」（个数、和、是否含某字符）时，大家就叫滑动窗口。
0.4 暴力 vs 优化：差在哪？（用数字感受）¶
假设数组长度 n = 10,000：
| 做法 | 大概要比较多少次 | 体感 |
|---|---|---|
| 两重循环（暴力） | n² ≈ 1 亿 | 明显卡 |
| 双指针 / 滑动窗口 | n ≈ 1 万 | 通常秒过 |
所以面试爱考：不是炫技巧，而是 数据一大，暴力就挂。
一、数组是怎么来的？（展开版）¶
1.1 为什么需要数组？（Why）¶
矛盾：计算机内存是一长条编了号的格子；现实里却是一组一组的数（成绩、股价、传感器读数）。
数组做的事：说「从门牌 base 开始，连续 n 格都是我的」，用 arr[0]…arr[n-1] 访问。
int[] scores = {85, 92, 78, 96, 88};
scores[2]; // 78，CPU 算：起始地址 + 2 × 每个 int 占几个字节
1.2 谁发明的？第一次用在哪里？（What）¶
重要前提：没有像「爱迪生发明灯泡」那样一个人发明数组。是 数学写法 → 机器怎么存 → 编程语言怎么写 三步走。
第一步：数学里早就有「带下标的一排数」¶
19 世纪起，代数里用 矩阵 表示二维表，例如 (a_{ij}) 表示第 i 行第 j 列。
「用下标访问有序数据」这个想法来自数学，不是某台计算机独有。
第二步：1945 年，冯·诺依曼架构——机器能「按地址跳」¶
冯·诺依曼（John von Neumann）提出：程序和数据都放在同一块内存里，按地址读写。
对程序员意味着：
想读「第 5 个数」→ 不必从第 1 个挨个数过来
→ 知道「起始地址 + 5 × 每个元素大小」就能一次读到
这就是今天 arr[i] 能 O(1) 访问的硬件基础。
第三步：1957 年，FORTRAN——语言里终于能写 A(1:100)¶
约翰·巴克斯（John Backus）在 IBM 带队做 FORTRAN I，第一个在高阶语言里提供 数组类型（还能多维），例如：
DIMENSION A(100)
A(1) = 3.14
之前用汇编要写「基址寄存器 + 偏移」，地址算错就全崩，普通人写不了大规模数值程序。
第一次真正「用数组干活」的场景¶
| 场景 | 在算什么 | 为什么适合数组 |
|---|---|---|
| 美军弹道表（二战后） | 不同角度、火药量下的炮弹落点 | 成千上万行数字表，要对整列/整行做运算 |
| 数值天气预报 | 网格上的温度、气压 | 二维网格 = 二维数组 |
| 解线性方程组 | 科学计算核心 | 矩阵就是二维数组 |
当时没有数组会怎样？ 人工「计算员」（多为女性）用机械计算器填表，慢且易错。
FORTRAN + 数组 + IBM 大型机，才把「填表」变成「程序批量算」。
时间线（一张表记住即可）¶
| 阶段 | 时间 | 谁 / 什么 | 贡献 |
|---|---|---|---|
| 数学 | 19 世纪 | 矩阵符号 | 下标表示法 |
| 硬件 | 1945 | 冯·诺依曼 | 线性地址、随机访问 |
| 语言 | 1957 | Backus / FORTRAN | 程序员可用的 array |
| 应用 | 1957–60s | 军方、气象局 | 弹道、天气、方程组 |
| 普及 | 之后 | COBOL、C、Java… | 表、行记录、像素、Tensor |
一句话：数组 = 连续内存 + 下标；FORTRAN 把它写进语言；最早大规模用来算 弹道表和天气预报 那种大表格。
When — 什么时候该用数组？¶
✅ 适合数组：
- 数据量已知或可预估，需要 O(1) 按下标读写
- 需要遍历、批量计算、排序
- 数据在内存里，追求缓存局部性（Cache-friendly）
❌ 不适合数组（考虑链表/哈希表等）：
- 频繁在中间插入/删除
- 大小不可预估且变化剧烈
- 主要是"查找某个值"而非"按位置访问"
Where — 数组在现实中的位置¶
即使你不写算法题，数组也无处不在：
- 数据库行存储：一行记录 = 各字段在磁盘/内存中连续排列
- 图像/视频：像素矩阵就是二维数组
- 游戏引擎：地图格子、碰撞检测网格
- 机器学习：Tensor 本质就是高维数组
- 日志/时序：按时间戳排序的 metrics 序列
- Java 的 ArrayList 底层、Python 的 list 底层（动态数组）
Who — 谁在用？¶
- 后端：批量处理订单 ID 列表、分页 offset 计算
- 数据工程：Spark/Flink 的分区数据、列式存储的列向量
- 前端：虚拟列表（Virtual List）用数组存可见项索引
- 游戏/图形：顶点坐标、纹理 UV 数组
- 嵌入式：传感器采样环形缓冲区（数组实现）
二、双指针¶
专题深读：双指针：11 个业务场景 + 手把手推演（对账、去重、MERGE JOIN、判环等）
本节只保留和数组、滑动窗口的衔接；三种指针的逐步推演见独立文档。
三、滑动窗口（从零搞懂 + 手把手推演）¶
3.1 和双指针有什么区别？¶
| 双指针（广义） | 滑动窗口（常指这一类） | |
|---|---|---|
| 关心什么 | 两个下标怎么动 | 连续 一段 [left, right] 里的统计 |
| 典型问法 | 两数之和、去重、合并 | 最长/最短 满足条件的子串、子数组 |
| 窗口长度 | 不一定连续关注区间 | 明确「框住一段」 |
很多题 既是双指针也是滑动窗口（都有 left/right），叫法不同而已。
3.2 名字从哪来？（和 TCP、限流的关系）¶
TCP 滑动窗口：发送方心里有个「框」，框里是「已发出还没确认」的数据包；确认一点，框就往前滑一点——限制在途流量。
API 限流里的滑动窗口：
「过去 60 秒内最多 100 次请求」——当前时刻往前数 60 秒是一个 会随时间移动的框，过期请求从框里划掉。
时间轴: ——|——|——|——|——|——|——→
[====60秒====]
↑ 框随「现在」往右滑
算法题里的滑动窗口：在数组/字符串上 用 left、right 框住连续段，逻辑类似「框可以变大变小」。
3.3 固定窗口 vs 可变窗口¶
| 类型 | 框的大小 | 例子 |
|---|---|---|
| 固定 | 长度 K 不变 | 最近 7 天销售额、长度为 K 的子数组最大和 |
| 可变 | 满足条件就缩 left，否则扩 right | 最长无重复子串、最小覆盖子串 |
3.4 手把手推演：最长无重复子串（LeetCode 3）¶
字符串：s = "abcabcbb"，求 最长 的、字符都不重复的 连续 子串。
暴力：每个起点试所有终点 → 大量重复检查。
滑动窗口：left 和 right 框住当前子串，用哈希表记「每个字符最后出现在哪」。
right 往右扩，遇到重复就把 left 跳到「重复字符上次位置 + 1」
步骤简写（子串 = s[left..right]）:
right=0 'a' 窗口 "a" max=1
right=1 'b' 窗口 "ab" max=2
right=2 'c' 窗口 "abc" max=3
right=3 'a' 重复！left 跳到 index('a')+1 → 窗口 "bca" max=3
right=4 'b' 重复！→ 窗口 "cab" ...
...
最终答案长度 3（"abc"）
两条铁律：
- right 只往右走（或循环里递增），每个字符最多 进窗口一次
- 不满足条件就缩 left，每个字符最多 出窗口一次
→ 一共 O(n) 步
业务对应：用户连续点击的页面路径，找「最长一段没有重复页面」；日志里最长无重复 traceId 的片段。
3.5 手把手推演：最小覆盖子串（LeetCode 76，思路）¶
字符串 S，找 T 里所有字符都出现过的 最短 连续子串。
- 扩 right：往窗口里加字符，直到「窗口已包含 T 的全部字符」
- 缩 left：在仍满足包含的前提下，尽量缩短左边
- 记录过程中的最短长度
业务对应：在一长段日志里，找 最短 一段同时出现 error、timeout、payment 的行，方便运维截片段。
3.6 现实业务场景（尽量具体）¶
| 场景 | 在干什么 | 和算法的对应 |
|---|---|---|
| API 限流 | 过去 60 秒请求 ≤ 100 | 时间轴上的滑动窗口计数 |
| 风控 | 5 分钟内同一 IP 登录失败 > 20 次 | 固定时长窗口内计数 |
| 监控告警 | 5 分钟错误率 > 1% | Prometheus rolling window |
| 报表 | 最近 7 天 GMV（今天进来、8 天前踢出） | 固定长度窗口求和 |
| 股票 | MA7 均线 | 窗口长度 7 的滑动平均 |
| 日志排障 | 最短包含多个关键字的片段 | 可变窗口 + 字符计数 |
| 播放器 | 缓冲区保留最近 N 秒数据 | 滑动缓冲 |
3.7 什么时候该想到「滑动窗口」？¶
题目里出现这些词，可以优先想：
- 连续 子数组 / 子串
- 最长 / 最短 满足某条件
- 窗口内 和、个数、是否包含某字符
- 至多 K 个重复、至少包含 某集合
若数据 无序 且问的是「任意两个数」而不是连续段 → 多半不是滑动窗口，而是哈希或排序+双指针。
四、刷题时怎么选？（决策树）¶
拿到数组/字符串题
│
├─ 问「连续一段」的最长/最短/和/个数？
│ └─ 是 → 优先想 【滑动窗口】或 【前缀和】
│
├─ 问「多次查询区间 [i,j] 的和」？
│ └─ 是 → 【前缀和】
│
├─ 数组已排序 + 找两个数 / 去重 / 合并 / 盛水？
│ └─ 是 → 【双指针】（对撞 / 快慢 / 逆向）
│
└─ 无序 + 找任意两数之和？
└─ 【哈希表】（LeetCode 1），不是双指针
| 技巧 | 一句话 | 典型前提 | 代表题 |
|---|---|---|---|
| 双指针 | 两个下标协同走，排除一大片 | 有序、原地、合并 | 167, 26, 11, 88 |
| 滑动窗口 | 框住连续段，扩 right 缩 left | 连续子串/子数组 | 3, 76, 209 |
| 前缀和 | 先算累计和，区间和 O(1) | 多次区间求和 | 560, 53 |
┌─────────────────────────────────┐
│ 数组（载体） │
│ 连续内存 + 下标 + 顺序扫描 │
└─────────────────────────────────┘
│
┌───────────────────────────┼───────────────────────────┐
▼ ▼ ▼
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ 双指针 │ │ 滑动窗口 │ │ 前缀和 │
│ 两个下标 │ │ left/right │ │ 预处理区间和 │
│ 协同移动 │ │ 维护区间状态 │ │ O(1) 查询 │
└─────────────┘ └─────────────┘ └─────────────┘
前缀和（补充 30 秒直觉）¶
问题：[1,2,3,4,5]，要问很多次「下标 1 到 3 的和」。
暴力：每次把 2+3+4 再算一遍。
前缀和：先算 prefix[i] = 前 i 个数的和，则 sum(1,3) = prefix[4] - prefix[1]，一次查询 O(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, right};
else if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}
// ============ 2. 快慢指针（原地去重）============
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;
}
// ============ 3. 滑动窗口（最长无重复子串）============
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (window.containsKey(c)) {
left = Math.max(left, window.get(c) + 1);
}
window.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// ============ 4. 前缀和（区间求和 O(1)）============
public int[] buildPrefix(int[] nums) {
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// sum[i..j] = prefix[j+1] - prefix[i]
return prefix;
}
六、必刷题目（15 题）¶
| # | 题目 | 难度 | 技巧 | 优先级 |
|---|---|---|---|---|
| 1 | 两数之和 | Easy | 哈希 | ⭐⭐⭐ |
| 15 | 三数之和 | Medium | 排序+对撞指针 | ⭐⭐⭐ |
| 26 | 删除有序数组重复项 | Easy | 快慢指针 | ⭐⭐ |
| 11 | 盛最多水的容器 | Medium | 对撞指针 | ⭐⭐⭐ |
| 3 | 无重复字符最长子串 | Medium | 滑动窗口 | ⭐⭐⭐ |
| 76 | 最小覆盖子串 | Hard | 滑动窗口 | ⭐⭐⭐ |
| 53 | 最大子数组和 | Medium | 前缀和/Kadane | ⭐⭐⭐ |
| 560 | 和为K的子数组 | Medium | 前缀和+哈希 | ⭐⭐⭐ |
| 239 | 滑动窗口最大值 | Hard | 单调队列 | ⭐⭐ |
| 42 | 接雨水 | Hard | 双指针/单调栈 | ⭐⭐⭐ |
| 88 | 合并两个有序数组 | Easy | 逆向双指针 | ⭐⭐ |
| 283 | 移动零 | Easy | 快慢指针 | ⭐⭐ |
| 438 | 找到字符串中所有字母异位词 | Medium | 滑动窗口 | ⭐⭐ |
| 54 | 螺旋矩阵 | Medium | 模拟/边界 | ⭐⭐ |
| 48 | 旋转图像 | Medium | 转置+翻转 | ⭐⭐ |
七、小结（背这几句就够）¶
| 主题 | 记住这一句 |
|---|---|
| 数组从哪来 | 数学下标 + 冯·诺依曼线性内存 + 1957 FORTRAN；最早算弹道表、天气预报 |
| 双指针 | 两个下标一起动，每步排除很多组合；要 有序 或 原地写 |
| 滑动窗口 | 框住 连续 一段，right 扩、left 缩；每个元素最多进出各一次 → O(n) |
| 和 TCP/限流 | 都是「一个会移动的框」；算法题是在 数组下标 上移动框 |
刷题口诀：
- 连续 + 最长/最短 → 滑动窗口
- 有序 + 两数/合并/去重 → 双指针
- 多次问区间和 → 前缀和
若仍懵：回到 §0 和 §二 2.2、§三 3.4 的手把手表格，对着 [2,7,11,15] 和 "abcabcbb" 自己在纸上画一遍指针移动。