数组与字符串 II

数组和字符串是面试考得最多的一类,而这第二轮就是题目不再是热身的地方。第一节数组课是简单模式下的双指针和滑动窗口;这一节是困难模式:一趟扫完就排好的三指针 partition、恰好保留 k 份的原地去重、不用额外内存的矩阵旋转、能拼出最大数的 comparator、完整的 2Sum → 3Sum → kSum 阶梯、合并 k 个有序流,以及在对数时间里求两个有序数组的中位数。下面每道题都能回溯到少数几个想法——双指针的两种方言、区域不变式、二分削减、heap——所以目标不是背下二十种解法,而是看穿它们身上其实是那四五个套路。

String 机制与两种双指针方言

动手做题前,两点 Java 常识决定你的代码是快还是意外变成二次方。第一,String 不可变。cur = cur + "1" 不是追加——它新建一个字符串并复制原有的每个字符,是 O(n)。放进循环里,你就悄悄写出了 O(n²)。逐字符构造结果时,用 StringBuilder(append 摊还 O(1))或预分配的 char[];读单个字符用 charAt(i),拿可变缓冲区用 toCharArray()。

这里有个值得点破的系统层面回声,面试官也会顺着问:不可变让 String 可以像 stateless 服务那样安全地被共享和扩容——没有调用方能在你脚下改它——而可变的 StringBuilder 是 stateful 的,必须由单个写入者独占。同样的不可变权衡,只是抬高了一个抽象层次。

整节课的主力是双指针,它有两种初学者常常糊在一起的方言:

还有一个下面处处用得上的词汇:区间语义。凡是用指针维护一个区域,先决定每一端是闭还是开——[)、[]、(]、()——并写成注释。partition 和滑动窗口里一半的差一位 bug,就是一个你从没钉死的边界。而任何滑动窗口题,动手前先回答三个问题:指针初始在哪、最终停在哪、答案在哪取(窗口刚合法时,还是窗口关闭之后)。

原地去重:保留一份、k 份或零份

一族四道题,数组有序(或「重复元素相邻」),区别只在保留几份。全都是 O(n) 时间、O(1) 空间。

保留一份(LC 26)。 slow/fast 最纯的形态:fast 扫描,只要 arr[fast] 和上一个保留的元素不同,就写到 slow。一个可爱的等价写法是把 StringBuilder 当隐式 Stack 用——新元素只在与当前最后一个字符不同时才 append:if (sb.length()==0 || i != sb.charAt(sb.length()-1)) sb.append(i);。这个「和栈顶比」的框架,可以推广到下面的无序变体。

保留 k 份(LC 80,k = 2)。 推广得很漂亮:令 slow = k,对每个 fast,只在它与已写前缀里往回数 k 个位置的元素不同时才保留。就这一个比较,保证任何值出现不超过 k 次。

public int dedup(int[] arr, int k) {
    if (arr == null || arr.length <= k) return arr == null ? 0 : arr.length;
    int slow = k;
    for (int fast = k; fast < arr.length; fast++) {
        if (arr[slow - k] != arr[fast]) {   // 与往回 k 格的元素不同 → 可以保留
            arr[slow++] = arr[fast];
        }
    }
    return slow;   // 新的逻辑长度
}

保留零份(删掉所有出现过重复的值)。两条路:建频率表 / freq[],只输出出现一次的;或用双指针扫描带一个「这段重复过吗」的 flag,好把整段重复的 run 一起跳过,而不是只跳一个。

无序,递归删相邻重复(LC 1047 一族)。 给定 a b b b c c a d e e,把相邻相等的 run 折叠一次得到 a a d,它自己又冒出新的相邻对(a a),还得继续折叠。干净的模型是 Stack(和栈顶比,匹配就 pop),一趟就把这种连锁折叠解决——笔记里说的递归,其实就是这个栈,只是把它变隐式了。

Partition:Move Zeroes 与 Dutch National Flag

Move Zeroes(LC 283) 保持每个非零元素的原始顺序,把所有零推到一侧——教科书式的稳定 slow/fast:让 fast 冲,每次落在非零上就写到 slow 并双双前进,最后把尾部填零。因为你只覆盖已经读过的位置,顺序得以保留,单趟 O(n)。

Sort Colors / 彩虹排序(LC 75) 是招牌题:只有 0/1/2 的数组,一趟排好。当取值集合很小且已知时,你可以用两趟 counting sort 做到 O(n)——但优雅的答案是 Dutch National Flag 三路 partition:三个指针 i, j, k 维护四个区域。

public void sortColors(int[] arr) {
    int i = 0, j = 0, k = arr.length - 1;
    // [0,i) = 0   [i,j) = 1   [j,k] = 未处理   (k,end] = 2
    while (j <= k) {
        if (arr[j] == 0) {
            swap(arr, i++, j++);   // 扩大 0 区,1 区整体右移
        } else if (arr[j] == 1) {
            j++;                    // 已经就位
        } else {
            swap(arr, j, k--);      // 把 2 送到末尾;j 不前进——换进来的值还没分类
        }
    }
}
private void swap(int[] a, int x, int y) { int t = a[x]; a[x] = a[y]; a[y] = t; }

面试官盯着的那一行:把 2 换到末尾后不能让 j 前进,因为你刚从位置 k 换回来的值仍是未处理的,下一轮还要分类。这不是玩具——它正是让 quicksort 在大量重复键下依然稳健的三路 partition(见 第 2 课排序)。推广也漂亮:排三个值就加一个指针;想只用两值逻辑排,把 1 和 2 都当「非 0」,先 partition 成 (0 | 12),再对 12 那段 partition 一次。

二分削减:用最少比较取胜

一簇题,从不问答案——谁都能找到——问的是用最少比较次数拿到答案。统一思想是一棵淘汰赛树:两两比较并复用结果。

同时求最大和最小。 朴素「打擂台」最多 2n 次比较。技巧:元素两两成对处理——先比一对(1 次),再把较大者和当前最大比、较小者和当前最小比(2 次)。每 2 个元素 3 次比较,总共 3n/2。(笔记里的一个细节:更新一个极值时往往能跳过另一个,所以最朴素版本实践中已经优于 2n——但成对处理才让 3n/2 这个界有保证。)

用最少 + 求 n 个数的和 是同一种形状,而答案无可回避:无论顺序累加还是成对树形,都恰好需要 n − 1 次加法。这是一个不错的清醒剂——二分削减并不总能帮忙。

最大和次大。 这里削减大放异彩。跑一场淘汰赛:冠军就是最大值,而亚军只可能是直接输给冠军的那些人之一。 搭起对阵表花 n − 1 次比较;冠军一路打了 ⌈log n⌉ 个对手,所以次大就是这些人里的最大——再花 ⌈log n⌉ − 1 次。合计 n − 1 + ⌈log n⌉,远低于朴素的 2n。

25 匹马的谜题 是同一原理套了个脑筋急转弯的壳:25 匹马,赛道一次跑 5 匹,没有秒表——用最少场次选出前 3。先跑 5 组各 5 匹(5 场),再让 5 个小组冠军同跑(第 6 场)得到总冠军并给各组排名。然后狠狠剪枝:只有还可能是第 2 或第 3 的马才留下,剩下一小撮候选,最后一场(第 7 场)定出第 2、第 3。7 场——答案是「每组前 m 名才是全局前 m 名的候选」的直接应用。

矩阵遍历:螺旋打印与旋转

螺旋顺序(LC 54) 和 Rotate Image(LC 48) 都是在不断收缩的正方形上做下标记账。螺旋:每一圈用左上角(offset)加 size 定义,走完四条边,再用 offset + 1、size - 2 向内递归或循环,直到 size 小于 1。

原地顺时针旋转 90° 有三种知名解法,最干净的是先转置,再翻转:

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 1) 沿主对角线转置
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    // 2) 每一行左右翻转 → 顺时针 90°
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1] = tmp;
        }
    }
}

两趟 O(n²)、O(1) 额外空间,几乎不可能写错。另外两种也值得能讲出来:按层四角一圈交换,一次搞定一圈的四个格子(从坐标映射 [r,c] → [c, n-1-r] 推出来);以及纯粹追着这些坐标变换做。追问部分:180° 就是上下翻转再左右翻转(或转置+翻转做两遍);而非正方形长方形无法原地旋转——输出的行列互换了,得开新矩阵并追踪两个 size。

自定义排序:让 comparator 干活

三道题,难点全在定义对的顺序,然后交给 Arrays.sort 或桶去做。

Custom Sort String(LC 791)——按 pattern 串里的优先级排 s 的字符,不在 pattern 里的排最后(按常规顺序)。comparator 分三种情况:两个字符都在 pattern(按 pattern 下标比)、只有一个在(在 pattern 的排前)、都不在(自然序)。但 O(n) 的答案根本不用比较排序:bucket / counting sort——统计字符频率,先按 pattern 顺序输出 pattern 里的字符,再输出其余的。

按首次/末次出现顺序排——把 2 1 3 5 7 2 9 7 2 6 重排,让相等的值按首次出现的顺序聚在一起(2 2 2 1 3 5 7 7 9 6)。建一个从「值 → 首次出现下标」的 HashMap(一个一对一的「pattern」,和上面 comparator 技巧同源),或者看出「把相等的东西聚起来同时保序」结构上就是 Move-Zeroes 的双指针按值应用一遍。

Largest Number(LC 179)——把一堆非负整数排列,使其拼接成的数最大([3,30,34,5,9] → 9534330)。洞察是一个成对 comparator:比较两个数 a 和 b 时,比的是字符串 a+b 与 b+a,而不是数字本身——"9"+"34" 胜过 "34"+"9"。

public String largestNumber(int[] nums) {
    if (nums == null || nums.length == 0) return "";
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);

    // b+a 排在 a+b 前 ⇒ 按拼接结果降序
    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));

    if (strs[0].charAt(0) == '0') return "0";   // 全是 0 → "0",不是 "000"
    StringBuilder sb = new StringBuilder();
    for (String s : strs) sb.append(s);
    return sb.toString();
}

别漏了前导零的 edge case:如果最大排列以 '0' 开头,说明所有元素都是零,答案是 "0",而不是一串零。

合并 K 个有序序列与外部排序

合并 k 个有序数组 是经典题,三种解法干净地对应一个复杂度/空间的权衡。先 clarify:升序?元素类型?有无重复?各自多大?资源限制(这真的是大数据 / 并行题吗)?

• 两两归并(merge-two,log k 层)。 沿二叉树一次归并两个数组,共 k−1 次归并,但有用的算法是按层数:每一层都碰全部 kn 个元素,log k 层,所以 O(kn·log k) 时间、O(kn) 空间。
• k 指针,朴素。 每个数组一个指针,反复取最小。在 k 个里找最小花 k,做 kn 次 → O(k²n)。k 路求最小是瓶颈。
• 大小为 k 的 min-heap。 把线性找最小换成 heap:O(nk·log k) 时间、O(k) 空间。每个面试官都会追问的坑——pop 出最小值后,它来自哪个数组? 光靠 HashMap<value, arrayIndex> 在有重复值时会崩,所以给每个条目包一个小 class 带上 {value, arrayIndex, indexInArray},heap 按 value 排。

合并 k 个有序链表(LC 23) 是同一个 heap 想法,而指针自带记账——ListNode 本来就知道自己的 next,不用 wrapper。先把每个链表头塞进 PriorityQueue,再反复 poll 出最小节点、接上、把它的后继 push 进去。heap 的机制见 第 6 课。

外部排序(「用 1GB 内存和两块 120GB 硬盘排 100GB」那道题) 是 merge-k 在物理世界的落地。单核排除了并行,于是:把 100GB 切成约 1000 块、每块约 100MB,在内存里各自排好写回成有序 run,再对这 1000 个 run 做 k 路归并。建模成 k·n = 100GB;内存占用约 max(k, n),在 √(100GB) 附近最小。主导开销是 k·n·(log n + log k) = 100GB · log(100GB)——run 的数量几乎不影响。要知道让这一切必要的 I/O 层级(机械盘约 50MB/s、SSD 约 500MB/s、内存约 10GB/s),而多机时这就是教科书式的 map-reduce。

k-Sum 阶梯:2Sum → 3Sum → kSum

2Sum(LC 1) 开局就有一个改变整道题的澄清问题:返回下标、值,还是布尔?数组有序吗?

• 有序 → 双指针 从两端往中间,按和与 target 的大小移动:O(n) 时间、O(1) 空间。
• 有序 → 二分 每个元素的补数:O(n·log n)。
• 无序 → 暴力 O(n²)(当允许任意个数相加时推广成 DFS / combination-sum)、排序后双指针,或一趟 HashMap 存已见值 → O(n)。

允许重复时,动手前先问面试官「一个答案」的定义——它会悄悄改变去重逻辑。

3Sum(LC 15) 是整条阶梯的模板:固定第一个元素,对其余跑 2Sum。先排序,内层双指针就是 O(n),重复三元组也容易跳过。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // 跳过重复锚点
        int lo = i + 1, hi = nums.length - 1, need = -nums[i];
        while (lo < hi) {
            if (nums[lo] + nums[hi] == need) {
                ans.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                while (lo < hi && nums[lo] == nums[lo + 1]) lo++;   // 跳过重复 lo
                while (lo < hi && nums[hi] == nums[hi - 1]) hi--;   // 跳过重复 hi
                lo++; hi--;
            } else if (nums[lo] + nums[hi] < need) {
                lo++;
            } else {
                hi--;
            }
        }
    }
    return ans;
}

4Sum(LC 18) 顺着归纳往上:双层循环固定两个元素,再对剩下的做 2Sum → O(n³),比朴素的 O(n⁴) 好。有个诱人的「先算所有 pair-sum,排序,再在 pair-sum 上做 2Sum」的想法,但不推荐——排 n² 个 pair-sum 要 O(n²·log(n²)),更糟的是你得处理一对里跨用同一元素的去重(3+5 会用到同一个下标两次吗?)。kSum 把递归推广:每层剥掉一个固定元素,一直降到 base-case 的 2Sum,把 O(nᵏ) 变成 O(n^(k−1))。

有序数组求交集

两个数组的公共元素(LC 349 / 350)。 先 clarify 老五样(有序?顺序?重复?各自多大?资源限制?)再选:

• 都有序 → 双指针,谁小移谁,任一走完就停:O(m + n)。
• 一个远小于另一个 → 二分 把 m 个元素分别在大数组里二分:O(m·log n)。因为 m + n = m(1 + n/m),它恰好在 1 + n/m < log n 时胜过双指针,也就是一个数组远大于另一个时。
• 无序 → 排短的那个((m+n)·log m 在 m < n 时优于 (m+n)·log n),或把短的丢进 HashSet 再流式扫另一个 → O(m + n),用较短数组建集合最省空间。

三个有序数组 扩成 三指针,谁小移谁,O(m + n + p)——严格优于做两次「两数组求交」。K 个有序数组 才有意思:k 指针、「谁小移谁」,但这时在 k 个里找最小的开销越来越大,于是用 min-heap(每步 O(log k))——同样要 wrapper,好知道每个值来自哪个数组。当 k 个指针都指向同一个值时它就在交集里;而 heap 只暴露最小值,所以另外维护一个全局 max(只增不减),当 min == max 时判定命中。另一条路是两两「两数组求交」做 k−1 次,按长度给数组排序,一旦某次交集空了就提前停——最坏 O(2kn)。当各数组大小悬殊时,把小数组的元素在大数组里二分。上述任一情况有重复,就 while 循环跳过相等的 run,或把结果丢进 set。

两个有序数组与数据流上的 order statistics

两个有序数组的第 k 小。 你可以归并到数够 k 个为止(O(k)),但不必真的归并——既然每步归并只是让较小的指针前进,那么 k 次前进就够了。

两个有序数组求中位数(LC 4) 用二分削减把它推到 O(log(min(m, n)))。把中位数化归为「求第 k 小」,每步比较两数组各自的第 k/2 个候选:第 k/2 个更小的那个数组,前 k/2 个里不可能含有全局第 k 小,直接丢掉,并把 k 减半。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int total = nums1.length + nums2.length;
    int left = (total + 1) / 2, right = (total + 2) / 2;   // +1/+2 处理奇偶(是第 k 个,不是下标)
    return (getKth(nums1, 0, nums2, 0, left)
          + getKth(nums1, 0, nums2, 0, right)) / 2.0;
}

private double getKth(int[] a, int i, int[] b, int j, int k) {
    if (i >= a.length) return b[j + k - 1];   // a 已耗尽
    if (j >= b.length) return a[i + k - 1];   // b 已耗尽
    if (k == 1) return Math.min(a[i], b[j]);

    int aMid = i + k / 2 - 1 < a.length ? a[i + k / 2 - 1] : Integer.MAX_VALUE;
    int bMid = j + k / 2 - 1 < b.length ? b[j + k / 2 - 1] : Integer.MAX_VALUE;

    return aMid < bMid
        ? getKth(a, i + k / 2, b, j, k - k / 2)   // 丢掉 a 的前 k/2
        : getKth(a, i, b, j + k / 2, k - k / 2);
}

corner case 就是整道题:某个数组比 k/2 短(用 Integer.MAX_VALUE 兜底,保证被丢的永远不是它)、某个数组耗尽,以及靠取第 left 个和第 right 个再平均来处理奇偶(用 k − k/2 让奇数总长也对)。若某个数组只有一个元素,直接二分它的插入位置比走通用递归更简单。

数据流求中位数(LC 295) 反过来:数字一个个来,你要能在任意时刻 O(1) 报出中位数。用两个 heap 把数据对半分——一个 max-heap lo 放较小一半,一个 min-heap hi 放较大一半。想用同一种 PriorityQueue 类型,就在 lo 里存取负的值。再平衡到两边大小相差至多 1;中位数就是较大 heap 的顶,或两个顶的平均。它诚实的局限,笔记里写着:如果流长到 heap 都放不下,这法子就废了——但若取值域有界(比如 0–9),退回到带累计计数的 counting sort,或存前缀累计数,这样就能二分找中位数的位置。

三数最大乘积(LC 628) 是个小号 order-statistics:有负数时,答案要么是最大的三个,要么是最小(最负)的两个乘最大的一个。排序,或用一对 heap / 一个 TreeSet 跟踪这五个极值——一个 min-heap 放大的、一个 max-heap 放小的。

Sliding Window Maximum:看着像 O(nk) 的 O(n)

LC 239——一个大小为 k 的窗口在数组上滑动,报出 n − k + 1 个位置各自的最大值。朴素做法对每个窗口重扫求最大:O((n − k + 1)·k)。把重扫换成 max-heap 能到 O((n − k + 1)·log k),但撞墙——除非刚好在堆顶,否则你没法便宜地删掉刚滑出窗口的那个元素。

对的结构是一个单调下标 deque,按值保持递减,于是队首永远是当前窗口的最大值。两个不变式维护它:从队首剔除已滑出窗口的下标;以及——关键一步——push 新下标前,从队尾弹掉所有值更小的下标,因为一个更小且更旧的元素,只要新来者还在,就再也不可能成为最大值。

public int[] maxSlidingWindow(int[] a, int k) {
    if (a == null || k <= 0) return new int[0];
    int n = a.length, ri = 0;
    int[] res = new int[n - k + 1];
    Deque<Integer> q = new ArrayDeque<>();   // 存下标,值从队首到队尾递减
    for (int i = 0; i < n; i++) {
        while (!q.isEmpty() && q.peek() < i - k + 1) q.poll();        // 剔除滑出窗口的
        while (!q.isEmpty() && a[q.peekLast()] < a[i]) q.pollLast();   // 弹掉没用的更小值
        q.offer(i);
        if (i >= k - 1) res[ri++] = a[q.peek()];   // 队首即窗口最大值
    }
    return res;
}

为什么是 O(n) 而不是 O(nk)?每个下标只进队一次、最多出队一次,整趟总工作量是 2n——摊还 O(n)。那个「一个大值清空整个 deque」看着贵的时刻,恰好换来后面很多步的便宜;这就是 amortized 分析的精髓。(存下标而不是值,让相等元素和窗口边界都无歧义。)

刷题清单