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

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。
  • 代价不对称:读快,中间增删慢。

原理流程

  1. 拿到首地址与元素宽度。
  2. 下标换算偏移量。
  3. 直接定位目标元素。

代码 / 图示

下标:  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)。

概念解释

  • 题目要求原地删除,尾部元素不保留。
  • 慢指针维护已保留区间的末尾。
  • 快指针遍历原数组。

原理流程

  1. slow=0。
  2. fast 遍历,a[fast] != val 时 a[slow++]=a[fast]。
  3. 返回 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)。

概念解释

  • 与移除元素同构:把非零值保留在前。
  • 补零阶段不改动前部。
  • 稳定:非零元素顺序不变。

原理流程

  1. slow 写非零元素。
  2. 扫描结束后从 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)。

概念解释

  • 有序性保证重复相邻,无需哈希判重。
  • 慢指针指向最后一个已保留元素。
  • 首元素天然保留。

原理流程

  1. slow=0。
  2. fast 从 1 扫描,a[fast] != a[slow] 时 a[++slow]=a[fast]。
  3. 返回 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 次。

原理流程

  1. slow 指向下一个写入位。
  2. fast 遍历,slow < k || a[slow-k] != a[fast] 则写入。
  3. 返回 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) 已满足条件。
  • 模板可套用到移除、去重、分区。

原理流程

  1. slow=0。
  2. fast 遍历,条件成立则写慢指针并后移。
  3. 结果前 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 尚未参与比较的元素。
  • 从后写:尾部空位先填,不冲突。
  • 剩余段直接拷贝。

原理流程

  1. i=m-1,j=n-1,k=m+n-1。
  2. 取较大值写入 k,对应指针前移。
  3. 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)。
  • 一次扫描完成分区。

原理流程

  1. left=0,mid=0,right=n-1。
  2. mid ≤ right:0 交换 left 后双进;2 交换 right 后 right 退、mid 不动;1 直接进。
  3. 结束即分区完成。

代码 / 示例

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 的取模。

原理流程

  1. k %= n。
  2. reverse(0, n-1)。
  3. 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。
  • 不回退:指针单向靠近。

原理流程

  1. l=0,r=n-1。
  2. 比较当前组合与目标。
  3. 按方向移动 l 或 r。
  4. 命中记录后继续找全部解。

代码 / 示例

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 开始按题目口径返回。
  • 题目保证有解。

原理流程

  1. l=0,r=n-1。
  2. 比较与 target。
  3. 命中返回;否则移动对应侧。

代码 / 示例

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)。
  • 移动长板:短板不变,宽度减小,容量不可能变大。
  • 移动短板:才可能遇到更高板。

原理流程

  1. l=0,r=n-1。
  2. 算容量更新最大值。
  3. 移动较短板侧指针。
  4. 相遇结束。

代码 / 示例

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) 空间。

概念解释

  • 过滤:只保留字母数字。
  • 大小写归一。
  • 两端向内比较。

原理流程

  1. l=0,r=n-1。
  2. 各自跳过无效字符。
  3. 归一化比较,不同返回 false。
  4. 相遇结束返回 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) 空间。

概念解释

  • 交换到中点即可。
  • 奇数长度中位元素自交换无意义。
  • 可推广到反转指定区间。

原理流程

  1. l=0,r=n-1。
  2. l<r 交换并移动。
  3. 结束即反转。

代码 / 示例

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。
  • 覆盖写:写位置不能未读先覆盖。

原理流程

  1. 先判空与长度下限。
  2. 每个指针移动后检查边界。
  3. 用最小用例手工走一遍。

代码 / 图示

风险点:
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,被覆盖值已扫描过。
  • 交换法:两类元素互换位置,互不覆盖。
  • 顺序稳定性由写法保证。

原理流程

  1. 确认 slow 与 fast 的先后关系。
  2. 覆盖场景保证 slow ≤ fast。
  3. 需保留被移除元素时改交换。

代码 / 图示

覆盖:[已保留 | 待扫描]
slow ≤ fast,写位不超前读位

常见误区

  • 误区:所有原地题都能覆盖写;正解:需要把剔除项放到后面保留时用交换。
  • 误区:覆盖写破坏顺序;正解:覆盖写天然保持保留元素顺序。

追问

  • Q:分区为左右两类且都要保留? A:用首尾交换或额外区间指针。
  • Q:覆盖后尾部旧值需要清理吗? A:按题目口径,通常只认前 slow 位。

02.2.1.1-017 重复元素在双指针题中如何处理?

一句话结论

有序数组重复值相邻:固定枚举点跳过相邻重复,命中解后双指针两侧继续跳过重复;无序场景用哈希集合记录已处理值。

概念解释

  • 排序去重:同层相等分支只取一次。
  • 命中后去重:避免收集相同组合。
  • 计数问题相反:要累加重复次数。

原理流程

  1. 外层枚举点与上一值相同则跳过。
  2. 命中解后移动到下一个不同值。
  3. 计数类问题累加出现次数。

代码 / 示例

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):只用若干指针与临时变量;递归栈、结果数组不计入原地口径时需单独说明;输入数组本身不算辅助空间。

概念解释

  • 辅助空间:函数内新建容器与变量。
  • 输出空间:题目要求返回的结果数组通常单列。
  • 争议口径:递归栈是否计入按题目约定。

原理流程

  1. 区分输入、输出、辅助三类空间。
  2. 统计辅助变量量级。
  3. 汇报口径写清。

代码 / 图示

双指针反转:辅助 O(1)
归并合并:临时数组 O(n)
返回新数组:输出空间单列

常见误区

  • 误区:用了几个指针就不算原地;正解:常数个变量即 O(1)。
  • 误区:输出数组也算辅助;正解:多数题面输出空间单列,需确认口径。

追问

  • Q:原地修改会不会影响调用方? A:会,引用传递下原数组被改,需确认允许。
  • Q:原地与稳定冲突吗? A:不冲突,覆盖写可保持稳定。

02.2.1.1-019 数组题常见边界用例有哪些?

一句话结论

必测:空数组、单元素、两元素、全部相等、严格有序、逆序、含重复、首尾命中、目标不存在;按题目补充负数与极值。

概念解释

  • 下限规模:验证初始指针与返回值。
  • 极端分布:验证去重与收敛。
  • 命中位置:首尾与中间。

原理流程

  1. 编码前列出边界清单。
  2. 每个用例手算预期。
  3. 跑代码对照修正。

代码 / 图示

[] / [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)。

概念解释

  • 暴力:两层循环枚举组合。
  • 双指针:每步排除一侧可能性。
  • 前提:有序或夹逼性质。

原理流程

  1. 写暴力枚举基线。
  2. 观察移动方向是否可由比较确定。
  3. 改为双指针并计入预处理代价。

代码 / 图示

暴力:for i, for j → O(n²)
双指针:l、r 单向移动 → O(n)
需有序:排序 O(n log n) 计入整体

常见误区

  • 误区:双指针一定比暴力快;正解:无序且无法排序时,双指针不成立。
  • 误区:忽略排序预处理;正解:整体复杂度取排序与扫描的高阶。

追问

  • Q:双指针空间优势? A:O(1) 额外空间,对比哈希 O(n)。
  • Q:什么情况双指针反而不合适? A:需要记录任意历史值、无序且不可排序的场景。