02.2.1.1 数组原地操作与快慢双指针
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.1 数组与双指针滑窗
02.2.1.1-001 数组为什么支持 O(1) 随机访问?
一句话结论
数组元素连续存储,按下标访问只需起始地址 + 下标 × 元素大小一次寻址,所以随机访问 O(1);插入删除需平移元素,为 O(n)。
概念解释
- 连续内存:元素地址等距排列。
- 寻址公式:
addr(i) = base + i·size。 - 代价不对称:读快,中间增删慢。
原理流程
- 拿到首地址与元素宽度。
- 下标换算偏移量。
- 直接定位目标元素。
代码 / 图示
下标: 0 1 2 3
地址: base base+s base+2s base+3s
a[i] 直接定位,无需遍历
常见误区
- 误区:数组所有操作都是 O(1);正解:只有随机访问 O(1),中间插入删除 O(n)。
- 误区:动态数组(ArrayList)也是连续存储;正解:底层数组连续,扩容时整体拷贝到新数组。
追问
- Q:链表访问第 i 个元素多少? A:O(i),需沿指针逐个走。
- Q:数组中间插入为什么慢? A:后续元素要整体后移一位。
02.2.1.1-002 移除元素(LC 27)怎么做?
一句话结论
快慢指针:慢指针指向写入位置,快指针扫描;遇到不等于目标的值就写到慢指针位置并后移,返回慢指针长度;时间 O(n),空间 O(1)。
概念解释
- 题目要求原地删除,尾部元素不保留。
- 慢指针维护已保留区间的末尾。
- 快指针遍历原数组。
原理流程
- slow=0。
- fast 遍历,
a[fast] != val时a[slow++]=a[fast]。 - 返回 slow。
代码 / 示例
public int removeElement(int[] a, int val) {
int slow = 0;
for (int fast = 0; fast < a.length; fast++) {
if (a[fast] != val) a[slow++] = a[fast];
}
return slow;
}
常见误区
- 误区:遇到目标就交换到末尾;正解:本题保留顺序用覆盖写即可,交换法适用于不要求保序的变体。
- 误区:返回数组长度前要清理尾部;正解:题目只要求前 slow 位有效,尾部可留旧值。
追问
- Q:数组为空? A:slow=0,直接返回 0。
- Q:全部等于目标? A:slow 保持 0,返回 0。
02.2.1.1-003 移动零(LC 283)怎么做?
一句话结论
先用快慢指针把非零元素移到前部,再把尾部补零;保持非零元素相对顺序,时间 O(n),空间 O(1)。
概念解释
- 与移除元素同构:把非零值保留在前。
- 补零阶段不改动前部。
- 稳定:非零元素顺序不变。
原理流程
- slow 写非零元素。
- 扫描结束后从 slow 到末尾填 0。
代码 / 示例
public void moveZeroes(int[] a) {
int slow = 0;
for (int fast = 0; fast < a.length; fast++) {
if (a[fast] != 0) a[slow++] = a[fast];
}
while (slow < a.length) a[slow++] = 0;
}
常见误区
- 误区:遇到零与后面非零逐个交换;正解:覆盖写更直接,交换法也可但需注意顺序。
- 误区:补零覆盖到前部;正解:只填 slow 之后的尾部。
追问
- Q:能否一次遍历边扫边交换? A:可以,非零时交换 slow 与 fast,slow 后移;等价保持稳定。
- Q:相对顺序必须保留吗? A:题目要求保留非零元素相对顺序。
02.2.1.1-004 有序数组去重(LC 26)怎么做?
一句话结论
有序数组重复值相邻;慢指针保留已去重区间,快指针遇到与慢指针值不同的新值,写入慢指针下一位置;时间 O(n),空间 O(1)。
概念解释
- 有序性保证重复相邻,无需哈希判重。
- 慢指针指向最后一个已保留元素。
- 首元素天然保留。
原理流程
- slow=0。
- fast 从 1 扫描,
a[fast] != a[slow]时a[++slow]=a[fast]。 - 返回 slow+1。
代码 / 示例
public int removeDuplicates(int[] a) {
if (a.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < a.length; fast++) {
if (a[fast] != a[slow]) a[++slow] = a[fast];
}
return slow + 1;
}
常见误区
- 误区:无序数组也能用相邻比较去重;正解:无序重复不相邻,需哈希或排序。
- 误区:返回 slow 而不是 slow+1;正解:slow 是下标,长度要加一。
追问
- Q:空数组返回多少? A:0。
- Q:全相同元素? A:slow 不动,返回 1。
02.2.1.1-005 去重保留至多两次(LC 80)怎么做?
一句话结论
通用写法:慢指针写入位置,快指针扫描;用 a[slow-2] 与当前值判断是否已出现两次,相同则跳过;时间 O(n),空间 O(1)。
概念解释
- 允许重复次数 k=2。
- 判断当前值与保留区倒数第 k 个是否相同。
- 推广到保留至多 k 次。
原理流程
- slow 指向下一个写入位。
- fast 遍历,
slow < k || a[slow-k] != a[fast]则写入。 - 返回 slow。
代码 / 示例
public int removeDuplicates(int[] a) {
int slow = 0;
for (int fast = 0; fast < a.length; fast++) {
if (slow < 2 || a[slow - 2] != a[fast]) a[slow++] = a[fast];
}
return slow;
}
常见误区
- 误区:用计数变量逐段统计;正解:与 slow-k 比较更简洁,且天然处理跨段重复。
- 误区:k 推广时改不动判断式;正解:把 2 换成 k 即可。
追问
- Q:保留至多一次怎么改? A:判断式改为
slow < 1 || a[slow-1] != a[fast]。 - Q:无序数组能这么做吗? A:不能,重复不相邻。
02.2.1.1-006 原地划分的通用快慢指针模板是什么?
一句话结论
满足条件的元素写入慢指针位置,不满足则跳过;慢指针始终指向已满足区间末尾,快指针负责扫描;一次扫描完成划分,O(n) 时间 O(1) 空间。
概念解释
- 条件:题目给定的保留/分区规则。
- 不变量:
[0, slow)已满足条件。 - 模板可套用到移除、去重、分区。
原理流程
- slow=0。
- fast 遍历,条件成立则写慢指针并后移。
- 结果前 slow 位满足条件。
代码 / 示例
int slow = 0;
for (int fast = 0; fast < a.length; fast++) {
if (condition(a[fast])) a[slow++] = a[fast];
}
常见误区
- 误区:慢指针需要交换;正解:覆盖写即可,交换用于需要把不满足项挪到后面的场景。
- 误区:条件判断写在慢指针侧;正解:条件按 fast 当前元素判定。
追问
- Q:要求保持原顺序吗? A:覆盖写天然稳定;不要求稳定时可用首尾交换的分区法。
- Q:划分成多类怎么办? A:多指针分别维护各区间边界。
02.2.1.1-007 合并两个有序数组(LC 88)原地怎么合?
一句话结论
nums1 尾部预留空间,从后往前用三个指针写较大值,避免从前向后覆盖未读元素;时间 O(m+n),空间 O(1)。
概念解释
- 从前写会覆盖 nums1 尚未参与比较的元素。
- 从后写:尾部空位先填,不冲突。
- 剩余段直接拷贝。
原理流程
- i=m-1,j=n-1,k=m+n-1。
- 取较大值写入 k,对应指针前移。
- j 有剩余则拷入前部。
代码 / 示例
public void merge(int[] a, int m, int[] b, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && a[i] > b[j]) a[k--] = a[i--];
else a[k--] = b[j--];
}
}
常见误区
- 误区:从前向后合并;正解:会覆盖 a 中未比较的元素。
- 误区:忘记 i 越界判断;正解:i 先耗尽时直接拷 b 剩余。
追问
- Q:b 剩余元素为什么不用再拷 a? A:a 剩余已在原位置。
- Q:稳定合并要求? A:相等时先取 a,保持相对顺序。
02.2.1.1-008 颜色分类(LC 75)三指针怎么做?
一句话结论
荷兰国旗问题:left 维护 0 区间末尾,right 维护 2 区间开头,mid 扫描;遇到 0 与 left 交换,遇到 2 与 right 交换,遇到 1 前进;O(n) 时间 O(1) 空间。
概念解释
- 三类值:0、1、2。
- 交换后需重新检查 mid 位置(从 right 换回来的可能是 0)。
- 一次扫描完成分区。
原理流程
- left=0,mid=0,right=n-1。
- mid ≤ right:0 交换 left 后双进;2 交换 right 后 right 退、mid 不动;1 直接进。
- 结束即分区完成。
代码 / 示例
public void sortColors(int[] a) {
int l = 0, m = 0, r = a.length - 1;
while (m <= r) {
if (a[m] == 0) swap(a, l++, m++);
else if (a[m] == 2) swap(a, m, r--);
else m++;
}
}
常见误区
- 误区:交换 2 后 m 也前进一步;正解:从 right 换回的值未判断,必须留在 m 复查。
- 误区:先计数再回填;正解:计数法也是 O(n),但三指针是原地一趟分区。
追问
- Q:为什么不用普通排序? A:值域固定为三类,三指针一趟完成,是线性分区。
- Q:交换 0 时 l 为什么能与 m 同步进? A:l 左侧均为 0,换回的 1 归 m 区间。
02.2.1.1-009 轮转数组(LC 189)三次反转怎么做?
一句话结论
右移 k 位:整体反转 → 前 k 段反转 → 后 n-k 段反转;k 先对 n 取模;时间 O(n),空间 O(1)。
概念解释
- 反转把尾部元素搬到头部。
- 三次拼接得到右移结果。
- 处理 k ≥ n 的取模。
原理流程
k %= n。- reverse(0, n-1)。
- reverse(0, k-1),reverse(k, n-1)。
代码 / 示例
public void rotate(int[] a, int k) {
int n = a.length;
k %= n;
reverse(a, 0, n - 1);
reverse(a, 0, k - 1);
reverse(a, k, n - 1);
}
void reverse(int[] a, int l, int r) {
while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
}
常见误区
- 误区:k 不做取模;正解:k 可能大于 n,必须先模 n。
- 误区:分段边界写错;正解:前一段 [0, k-1],后一段 [k, n-1]。
追问
- Q:额外数组做法? A:新数组
(i+k)%n落位,空间 O(n)。 - Q:右移与左移区别? A:左移 k 等价右移 n-k,分段点相应调整。
02.2.1.1-010 相向双指针框架怎么写?
一句话结论
l 在左端、r 在右端,按比较结果向中间收敛;每次移动一侧指针,区间逐步缩小;前提是数组有序或问题具有夹逼性质,O(n) 扫描 O(1) 空间。
概念解释
- 移动方向:和偏小移 l,偏大移 r。
- 终止:l ≥ r。
- 不回退:指针单向靠近。
原理流程
- l=0,r=n-1。
- 比较当前组合与目标。
- 按方向移动 l 或 r。
- 命中记录后继续找全部解。
代码 / 示例
int l = 0, r = n - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) { /* 记录 */ l++; r--; }
else if (s < target) l++;
else r--;
}
常见误区
- 误区:无序数组直接相向;正解:无序时移动方向无法确定,需先排序或用哈希。
- 误区:命中后只移一侧;正解:找全部解时两侧都要移动并去重。
追问
- Q:什么时候只移一侧? A:唯一解场景命中即可返回。
- Q:双指针为什么 O(n)? A:l 只增、r 只减,合计移动不超过 n 次。
02.2.1.1-011 两数之和 II 有序输入(LC 167)怎么做?
一句话结论
数组已升序,相向双指针夹逼:和小移左、和大移右,命中即返回下标;时间 O(n),空间 O(1),优于哈希的 O(n) 空间。
概念解释
- 有序保证移动方向唯一。
- 下标从 1 开始按题目口径返回。
- 题目保证有解。
原理流程
- l=0,r=n-1。
- 比较与 target。
- 命中返回;否则移动对应侧。
代码 / 示例
public int[] twoSum(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return new int[]{l + 1, r + 1};
if (s < target) l++; else r--;
}
return new int[]{-1, -1};
}
常见误区
- 误区:仍用哈希表;正解:有序前提下双指针省空间。
- 误区:返回 0 基下标;正解:按题目口径转换。
追问
- Q:有重复元素会影响吗? A:题目保证唯一解,命中即返回。
- Q:无序版本用什么? A:哈希表边查边放 O(n)/O(n)。
02.2.1.1-012 盛最多水的容器(LC 11)怎么做?
一句话结论
相向双指针:容量由两板较短板与宽度决定;每次移动较短板指针(移动长板不会增高短板,宽度还变小);O(n) 时间 O(1) 空间。
概念解释
- 容量 = min(h[l], h[r]) × (r-l)。
- 移动长板:短板不变,宽度减小,容量不可能变大。
- 移动短板:才可能遇到更高板。
原理流程
- l=0,r=n-1。
- 算容量更新最大值。
- 移动较短板侧指针。
- 相遇结束。
代码 / 示例
public int maxArea(int[] h) {
int l = 0, r = h.length - 1, ans = 0;
while (l < r) {
int area = Math.min(h[l], h[r]) * (r - l);
ans = Math.max(ans, area);
if (h[l] < h[r]) l++; else r--;
}
return ans;
}
常见误区
- 误区:两板一起移动;正解:只移较短板,保留另一侧高度。
- 误区:容量用长板计算;正解:水由短板决定。
追问
- Q:为什么不能移动长板? A:宽度减小、短板不变,容量只减不增。
- Q:暴力解法复杂度? A:O(n²) 枚举所有边对。
02.2.1.1-013 验证回文串(LC 125)怎么做?
一句话结论
相向双指针跳过非字母数字字符,统一大小写后比较;不一致即非回文;O(n) 时间 O(1) 空间。
概念解释
- 过滤:只保留字母数字。
- 大小写归一。
- 两端向内比较。
原理流程
- l=0,r=n-1。
- 各自跳过无效字符。
- 归一化比较,不同返回 false。
- 相遇结束返回 true。
代码 / 示例
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
if (Character.toLowerCase(s.charAt(l++)) != Character.toLowerCase(s.charAt(r--))) return false;
}
return true;
}
常见误区
- 误区:先过滤生成新串;正解:原地双指针 O(1) 额外空间。
- 误区:跳过字符后不复查越界;正解:内层跳过循环也要带 l<r 条件。
追问
- Q:数字参与比较吗? A:题目口径内字母数字都保留,数字按字符比较。
- Q:空串或单字符? A:直接返回 true。
02.2.1.1-014 反转数组怎么写,边界在哪?
一句话结论
相向双指针交换对称位置,l<r 时交换并内移;偶数对全部交换,奇数中间元素不动;O(n) 时间 O(1) 空间。
概念解释
- 交换到中点即可。
- 奇数长度中位元素自交换无意义。
- 可推广到反转指定区间。
原理流程
- l=0,r=n-1。
- l<r 交换并移动。
- 结束即反转。
代码 / 示例
void reverse(int[] a) {
int l = 0, r = a.length - 1;
while (l < r) {
int t = a[l]; a[l++] = a[r]; a[r--] = t;
}
}
常见误区
- 误区:循环条件写 l ≤ r;正解:相等时自交换无害但多余,l<r 即可。
- 误区:用额外数组逐位拷贝;正解:原地交换省空间。
追问
- Q:反转区间 [l, r] 呢? A:把端点作为参数传入,同样相向交换。
- Q:字符串反转注意什么? A:字符串不可变,需转字符数组。
02.2.1.1-015 数组题中常见的越界风险有哪些?
一句话结论
越界多发生在:空数组取 [0]、右端点 -1、双指针越过边界、fast 读在 slow 写之后;编码前先列空与单元素用例。
概念解释
- 空数组:长度 0,任何下标访问都越界。
- 端点:r = n-1,移动后需检查 ≥0。
- 覆盖写:写位置不能未读先覆盖。
原理流程
- 先判空与长度下限。
- 每个指针移动后检查边界。
- 用最小用例手工走一遍。
代码 / 图示
风险点:
a[0] 当 n=0
a[r--] 当 r=0
slow-2 当 slow<2
交换前校验两侧下标
常见误区
- 误区:默认数组非空;正解:函数入口先判空。
- 误区:条件判断短路顺序随意;正解:先判下标合法再取值。
追问
- Q:Java 数组越界抛什么? A:ArrayIndexOutOfBoundsException。
- Q:二分中点怎么防溢出? A:
l + (r-l)/2。
02.2.1.1-016 原地覆盖写会不会丢失未处理元素?
一句话结论
只要写位置 slow 不超过读位置 fast(覆盖写),被覆盖的都是已处理过的元素,不会丢失;若写快于读则必须先交换而非覆盖。
概念解释
- 覆盖写:slow ≤ fast,被覆盖值已扫描过。
- 交换法:两类元素互换位置,互不覆盖。
- 顺序稳定性由写法保证。
原理流程
- 确认 slow 与 fast 的先后关系。
- 覆盖场景保证 slow ≤ fast。
- 需保留被移除元素时改交换。
代码 / 图示
覆盖:[已保留 | 待扫描]
slow ≤ fast,写位不超前读位
常见误区
- 误区:所有原地题都能覆盖写;正解:需要把剔除项放到后面保留时用交换。
- 误区:覆盖写破坏顺序;正解:覆盖写天然保持保留元素顺序。
追问
- Q:分区为左右两类且都要保留? A:用首尾交换或额外区间指针。
- Q:覆盖后尾部旧值需要清理吗? A:按题目口径,通常只认前 slow 位。
02.2.1.1-017 重复元素在双指针题中如何处理?
一句话结论
有序数组重复值相邻:固定枚举点跳过相邻重复,命中解后双指针两侧继续跳过重复;无序场景用哈希集合记录已处理值。
概念解释
- 排序去重:同层相等分支只取一次。
- 命中后去重:避免收集相同组合。
- 计数问题相反:要累加重复次数。
原理流程
- 外层枚举点与上一值相同则跳过。
- 命中解后移动到下一个不同值。
- 计数类问题累加出现次数。
代码 / 示例
if (i > 0 && a[i] == a[i - 1]) continue; // 外层去重
while (l < r && a[l] == a[l + 1]) l++; // 内层去重
while (l < r && a[r] == a[r - 1]) r--;
常见误区
- 误区:去重位置只写一处;正解:固定点与指针命中处都要去重。
- 误区:计数题也去重;正解:求个数时重复要计入,不能跳过。
追问
- Q:无序数组组合去重怎么做? A:排序后相邻去重,或结果序列化后入集合判重。
- Q:两数之和重复对怎么返回? A:按题目要求返回任意一对或全部组合。
02.2.1.1-018 数组原地算法的空间复杂度口径是什么?
一句话结论
原地算法辅助空间 O(1):只用若干指针与临时变量;递归栈、结果数组不计入原地口径时需单独说明;输入数组本身不算辅助空间。
概念解释
- 辅助空间:函数内新建容器与变量。
- 输出空间:题目要求返回的结果数组通常单列。
- 争议口径:递归栈是否计入按题目约定。
原理流程
- 区分输入、输出、辅助三类空间。
- 统计辅助变量量级。
- 汇报口径写清。
代码 / 图示
双指针反转:辅助 O(1)
归并合并:临时数组 O(n)
返回新数组:输出空间单列
常见误区
- 误区:用了几个指针就不算原地;正解:常数个变量即 O(1)。
- 误区:输出数组也算辅助;正解:多数题面输出空间单列,需确认口径。
追问
- Q:原地修改会不会影响调用方? A:会,引用传递下原数组被改,需确认允许。
- Q:原地与稳定冲突吗? A:不冲突,覆盖写可保持稳定。
02.2.1.1-019 数组题常见边界用例有哪些?
一句话结论
必测:空数组、单元素、两元素、全部相等、严格有序、逆序、含重复、首尾命中、目标不存在;按题目补充负数与极值。
概念解释
- 下限规模:验证初始指针与返回值。
- 极端分布:验证去重与收敛。
- 命中位置:首尾与中间。
原理流程
- 编码前列出边界清单。
- 每个用例手算预期。
- 跑代码对照修正。
代码 / 图示
[] / [x] / [x,x] / [1,2,3] / [3,2,1]
目标在首 / 在尾 / 不存在
含 0、负数、重复值
常见误区
- 误区:只测正常多元素用例;正解:边界用例是面试官重点检查项。
- 误区:去重题不测全相同;正解:全相同是最容易暴露返回值错误的用例。
追问
- Q:两元素指针怎么动? A:l=0、r=1,比较后一侧移动即相遇。
- Q:空输入返回什么类型? A:按题目约定,常见为 0、false 或空列表。
02.2.1.1-020 双指针解法相对暴力枚举赢在哪?
一句话结论
暴力枚举所有元素对是 O(n²);双指针利用有序性或位置性质让指针单向移动,扫描 O(n),把内层枚举消掉,代价是可能需要先排序 O(n log n)。
概念解释
- 暴力:两层循环枚举组合。
- 双指针:每步排除一侧可能性。
- 前提:有序或夹逼性质。
原理流程
- 写暴力枚举基线。
- 观察移动方向是否可由比较确定。
- 改为双指针并计入预处理代价。
代码 / 图示
暴力:for i, for j → O(n²)
双指针:l、r 单向移动 → O(n)
需有序:排序 O(n log n) 计入整体
常见误区
- 误区:双指针一定比暴力快;正解:无序且无法排序时,双指针不成立。
- 误区:忽略排序预处理;正解:整体复杂度取排序与扫描的高阶。
追问
- Q:双指针空间优势? A:O(1) 额外空间,对比哈希 O(n)。
- Q:什么情况双指针反而不合适? A:需要记录任意历史值、无序且不可排序的场景。