数组与字符串

数组与字符串是 coding 面试里出现频率最高的一类,也是候选人最容易低估的一类。题目看着都很机械——删掉一个字符、翻转单词、判断 anagram——但每一道背后都藏着两个决定:你怎么表示这份数据,以及用哪种指针纪律去遍历它。这节课把整个家族系统化:不可变字符串背后的 char[] 思维、slow/fast 原地压缩套路、「先整体翻转再局部翻转」的恒等式、用频率数组搞定 anagram 与 permutation,以及撑起一半子串题的滑动窗口。

基础:char[]、不可变性与两种指针

在任何具体题目之前,这节课先把数据表示讲清楚。怎么表示一个数?可以用 array、String,也可以用 LinkedList——而做加减乘除时 LinkedList 最顺手,因为进位可以 O(1) 地往头上接。经典画面:"123" 按位存成 3 → 2 → 1 → null;而 "00456" 这种带前导零的输入,得先 pre-processing 一趟才敢用。

具体到字符串,有三个事实主导所有决策。第一,Java 的 String 不可变,底层是 char[]。第二,substring(start, end) 是 O(n)——它在半开区间 [start, end) 上新建一份字符串,并不免费。第三,s1 + s2 是 O(m + n),放进循环就悄悄变成 O(n²)。逃生舱是 StringBuilder(append、insert、deleteCharAt、charAt、toString),它的 append 是 amortized O(1)。两个转换值得肌肉记忆:进去是 str.toCharArray(),出来是 new String(ca, start, len) 或 String.valueOf(ca)。

正是这份不可变性,让双指针成为这里的主力技术。它有两种形态,选对哪一种就赢了一半:

• slow / fast——同向移动。fast 负责读和探索,slow 负责写答案。这是原地压缩:删除、去重、空格规整。
• left / right——两端相向逼近中间。这是翻转、旋转、判回文。

用 slow/fast 做原地删除

最纯的 slow/fast 题:删除某个字符的所有出现——比如把 "yougetoffer" 里的 'f' 和 'o' 删掉。两种干净写法:用 StringBuilder 一趟扫(是保留字符才 append),或者转成 char[] 让 fast 读、slow 写。数组版是必须内化的那个,因为它引出了所有删除题共享的不变式。

public String removeChar(String s, char c) {
    if (s == null || s.length() == 0) return s;
    char[] ca = s.toCharArray();
    int slow = 0;
    for (int fast = 0; fast < s.length(); fast++) {
        if (ca[fast] != c) {          // 留下要的,丢掉其余
            ca[slow++] = ca[fast];
        }
    }
    return new String(ca, 0, slow);   // [0, slow) 就是压缩后的答案
}

一个值得知道的变体:如果不要求保序,可以改成把不要的字符 swap 到末尾再收缩边界。它仍是 O(n) 但不稳定——留下来的元素顺序会乱。这恰好是 LC 27 Remove Element 在「不需要保序」时的最优解。

有序数组去重——保留 k 个

同样的骨架,换个比较对象。要在有序数组里去重、每个值最多保留 k 个,就拿 ca[fast] 和 ca[slow - k] 比:不相等,这个元素就配得一个位置。两个指针都从 k 起步。一个参数统一了两道名题——LC 26(保留一个,k = 1)和 LC 80(保留两个,k = 2)——而「fast 与 slow − k 比较」正是让它可推广的关键。

规整空格

把开头、结尾、以及中间重复的空格都压成单词之间的单个空格:"␣␣␣you␣␣␣get␣offer␣␣" → "you␣get␣offer"。slow/fast 循环在空格属于「开头空格」或「紧跟另一个空格」时跳过(ca[fast] == ' ' && (fast == 0 || ca[fast-1] == ' ') → 跳)。剩一步后处理:结果末尾可能残留一个空格,有就砍掉。这个小助手——就叫 removeDuplicateSpaces——会在下面的 reverse-words 里原样复用。

翻转家族

翻转字符串(LC 344)是 left/right 的原型:swap(ca, i++, j--) 直到两针相遇。它也是很好的递归练习——可以写成尾递归(先 swap 再向内递归),也可以写成前/后序递归,但注意笔记标的坑:如果你在递归前改了 i、j,递归后必须改回来,因为整条调用栈共享同一个数组。

LC 151 Reverse Words in a String("you get offer" → "offer get you")有三种角度。最快写的用 split(" ") 再用 StringBuilder 倒序拼——但小心多个空格会让 split 吐出空串,得跳过 ""。真正加分的是 O(1) 额外空间的三步走:先翻转整个 char 数组,再把每个单词翻回来,最后压掉空格。双指针找每个单词的边界,而最后一个单词需要额外补一次翻转,因为它后面没有空格来触发。

public String reverseWords(String s) {
    if (s == null || s.length() == 0) return "";
    char[] ca = s.toCharArray();
    reverse(ca, 0, ca.length - 1);      // 1. 翻转整句
    int i = 0, j;
    for (j = 0; j < ca.length; j++) {   // 2. 把每个单词翻回来
        if (ca[j] == ' ') {
            reverse(ca, i, j - 1);
            i = j + 1;
        }
    }
    reverse(ca, i, j - 1);              // 最后一个单词后面没有空格触发它
    return removeDuplicateSpaces(ca);       // 3. 压掉多余空格
}

private void reverse(char[] ca, int i, int j) {
    while (i < j) {
        char t = ca[i]; ca[i] = ca[j]; ca[j] = t;
        i++; j--;
    }
}

第三种角度是特殊 pattern:有些输入把一个多词短语当作一个 token——"Let's go to new york" → "new york to go Let's",其中 "new york" 保持完整。配方一样:先整体翻转,再用标志位切 token 做局部翻转,并对最后一个 token 做后处理。

字符串旋转 / 移位("abcdefg" → "efgabcd")是完全同一个恒等式。先 offset %= n,再做三次翻转:翻 [0, n-offset-1]、翻 [n-offset, n-1]、再翻整个。「三次翻转旋转」和 reverse-words 是同一招换了件外衣。

编码、解码与字符串数学

这一簇是把字符变成结构化输出再变回来。Run-length encoding——"aaabbbbccdeee" → "a3b4c2d1e3"——就是一趟扫描加一个 run 计数器,字符一变就 flush 出 char + count。LC 38 Count and Say 是把 run-length encoding 递归地套上去:每一行都由「run-length 描述上一行」得来。遍历上一个字符串,数连续相同字符,变化时 append count 再 append char(循环结束后再 flush 一次)。笔记还把 LC 191 也归到这里当作编解码相关的练习。

LC 8 String to Integer(atoi) 是数学主力:跳过前导空格、读一个可选的 +/- 号,然后累加数字——而全部难点在溢出。要在乘之前守门:如果 (Integer.MAX_VALUE - digit) / 10 < total,就按符号 clamp 到 MAX_VALUE 或 MIN_VALUE,别让 total = 10 * total + digit 溢出回绕。这种「先检查再增长」的纪律就是考点。

URL 空格替换(LintCode 的 Space Replacement)在 ' ' ↔ "%20" 之间转。因为 "%20" 比空格长,干净的原地做法是先数空格,再从后往前写,这样永远不会覆盖还没读的字符。这个「从末尾往前填」的思路,和数组原地合并背后是同一个。

模式匹配:strStr 与 DP 匹配

LC 28 Implement strStr()——找 needle 在 haystack 里第一次出现的下标。记住 Java 里 substring 是 O(n),切片来比是浪费,应该按下标扫。朴素双重循环 O(m·n),但外层指针只需跑到 n − m(再往后 needle 塞不下)。

public int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();   // 缓存长度
    for (int i = 0; i <= n - m; i++) {                 // 到 n - m 为止,再往后塞不下
        int j;
        for (j = 0; j < m; j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) break;
        }
        if (j == m) return i;                          // needle 全部匹配
    }
    return -1;
}

升级版是 Rabin-Karp:维护当前窗口的 rolling hash,每步减掉滑出的字符、加上滑入的字符——每个位置只比一次 hash,O(n − m + 1 + m) = O(n)。要主动交代的 caveat:pattern 太长会有 hash collision,所以先比长度,再比 hash,命中后再逐字符 verify。同样的扫描也能从 String 推广到链表(用 .next 和 size()),或一次搜多个 needle。

这一组里最难的两道是 DP 匹配,dp[i][j] 回答「s[0..i) 与 p[0..j) 是否匹配?」LC 44 Wildcard Matching:'?' 匹配恰好一个字符(dp[i][j] = dp[i-1][j-1]),'*' 匹配空或多一个(dp[i][j] = dp[i][j-1] || dp[i-1][j]);初始化第一行,让一串 '*' 能匹配空串。LC 10 Regular Expression Matching 更难,因为 '*' 绑定前一个字符:"a*" 可以算作空(dp[i][j-2]),或者当前字符匹配 a、或 pattern 是 '.' 时算作扩展(dp[i-1][j])。认出 state 定义就赢了大半;dp[i][j] 定死之后,转移只是分类讨论。

Permutation

LC 46 Permutations(无重复)是 swap-based DFS:每一层,i 从 level 到 n-1,把 i swap 到 level,递归 level + 1,再 swap 回来。为什么要 swap 回来?因为 Java 数组是按引用值传的——递归改的是同一个数组,你必须还原(经典 backtracking)。如果每层都新建一个 string,就没什么要撤销的。

LC 47 Permutations II(有重复)先排序让相同值相邻,再对选择去重。两种做法:每层一个 HashSet 拒绝这个位置已经试过的值,或者用 used[] 布尔数组加经典跳过规则。布尔版的微妙之处:只跳过那些「相同前驱在当前路径上还没被用」的重复——这样每个相等块只保留一种排列顺序,因为一个只能检测「重复」的开关,没法同时告诉你「哪一份已经被用过」。

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);                       // 让相同值挨在一起
    backtrack(res, new ArrayList<>(), nums, new boolean[nums.length]);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> temp,
                       int[] nums, boolean[] used) {
    if (temp.size() == nums.length) {
        res.add(new ArrayList<>(temp));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // 跳过「相同前驱在本路径上还没被用」的重复
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
        used[i] = true;
        temp.add(nums[i]);
        backtrack(res, temp, nums, used);
        used[i] = false;                     // 撤销——数组是共享的
        temp.remove(temp.size() - 1);
    }
}

Anagram、回文与 Isomorphic

LC 242 Valid Anagram 是频率数组的招牌:走第一个串给 int[26] 做 ++,走第二个串做 --,最后确认每个桶都是 0。O(n) 时间、O(1) 空间(26、52、128 或 256,看字母表)。先比长度快速否决,或者中途逮到某个桶变负就返回。笔记里的替代法:两个串都排序再比(O(n log n)),或用 base-26 的 char hash——但 26 个 a 会和一个 b 撞,所以裸的多项式 hash 需要辅助检查(比如比长度)。当题目变成「在一个串里找 pattern 的所有 anagram」(LC 438),配方就是滑动窗口 + char hashing:一个定宽窗口,拿它的频率表去匹配 pattern。

LC 125 Valid Palindrome 是 left/right 相向逼近:两端各自跳过非字母数字,转小写,比较。一行流的写法——replaceAll("[^A-Za-z0-9]", "").toLowerCase() 再和它的 reverse 比——读起来干净,但要为两个临时串付 O(n) 额外空间。

LC 5 Longest Palindromic Substring 反过来做:从中心向外扩。对每个下标试奇数中心 (i, i) 和偶数中心 (i, i+1),两端相等就往外扩。while 越界后,回文长度是 k - j - 1——注意这个 off-by-one,因为 j 和 k 各自都已经多走了一步。O(n²) 时间、O(1) 空间;Manacher 是 O(n) 的 follow-up,但很少要求。

LC 205 Isomorphic Strings 看着像单 map 题,其实不是:单个 char → char 的 map 会挂,因为映射必须是双射——两个源字符不能塌到同一个目标。用两个 map(或把每个字符映射到它最近出现的 index 再比较这些 index)来强制双向一致。

LC 9 Palindrome Number 证明你根本不用字符串:只翻转一半的数位。while (x > rev) 里造 rev = rev*10 + x%10、缩 x /= 10;开头处理尾零陷阱(x != 0 && x % 10 == 0 → 不是回文,因为反过来会多个前导零),最后返回 x == rev || x == rev/10 同时覆盖偶数位和奇数位。

字符串上的滑动窗口

两个信号出卖了滑动窗口题:出现「子串」,以及一个最高级——「最长」或「满足…的最短」。套路永远一样:fast 指针无脑向前走,[slow, fast] 维持成一个合法窗口,而重复/成员判断用 HashSet 或 HashMap 保持 O(1)。

LC 3 Longest Substring Without Repeating Characters 用 HashMap 记每个字符最近出现的 index。遇到重复时把 slow 跳到 max(slow, lastIndex + 1)——这个 max 很关键,因为一个躺在当前 slow 后面的旧 index 绝不能把窗口往回拽。这里 HashMap 胜过 HashSet,恰恰因为它带着 index,slow 可以一跳到位而不用一步步爬。

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    HashMap<Character, Integer> map = new HashMap<>();
    int max = 0;
    for (int fast = 0, slow = 0; fast < s.length(); fast++) {
        char c = s.charAt(fast);
        if (map.containsKey(c)) {
            slow = Math.max(slow, map.get(c) + 1);   // 跳过旧的那份,绝不后退
        }
        map.put(c, fast);
        max = Math.max(max, fast - slow + 1);        // [slow, fast] 无重复
    }
    return max;
}

「最多 k 个重复字符」的变体只是换了失效规则:当某个字符的计数超过 k,就让 slow 往前爬、同时在 map 里减计数,直到那个字符回到预算之内。窗口骨架一样,只是收缩触发条件不同。

LC 76 Minimum Window Substring 是这一家族的 boss:找 s 中包含 t 全部字符的最短窗口。为 t 建一个 need-count map,再加一个「已满足需求数」count;向右扩 right 直到窗口覆盖 t(count == t.length()),然后向右收 left,在仍覆盖的前提下不断记录最小值。

public String minWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray())
        need.put(c, need.getOrDefault(c, 0) + 1);

    int left = 0, minLeft = 0, minLen = s.length() + 1, count = 0;
    for (int right = 0; right < s.length(); right++) {
        char r = s.charAt(right);
        if (need.containsKey(r)) {
            need.put(r, need.get(r) - 1);
            if (need.get(r) >= 0) count++;     // 只数还需要的字符
        }
        while (count == t.length()) {           // 窗口已覆盖 t → 尝试收缩
            if (right - left + 1 < minLen) {
                minLeft = left;
                minLen = right - left + 1;
            }
            char l = s.charAt(left);
            if (need.containsKey(l)) {
                need.put(l, need.get(l) + 1);
                if (need.get(l) > 0) count--;   // 丢掉的是真正需要的字符
            }
            left++;
        }
    }
    return minLen == s.length() + 1 ? "" : s.substring(minLeft, minLeft + minLen);
}

刷题清单