想象你接管了剧场后台的舞台总监工作。你要管理的是一整面墙的储物柜——它们整整齐齐排成一列，每个柜门都有编号，里面装着对应的道具。这一排储物柜，就是“数组”。你还管着一串串珍珠名牌：每颗珍珠上烙着一个字，串成演员的名字，穿好的珠串就是“字符串”。 面试考察数组与字符串，本质上考察的就是你这位“后台总监”的调度智慧：如何利用储物柜连续排列的特点快速取物？如何在两排道具之间高效找到匹配的一对？如何在不重新穿整条珠串的前提下完成名字的查验与拼接？掌握了这套“后台调度术”，任何面试题都不过是换了个柜门编号而已。 这篇文章从储物柜讲起，带你走过数组基础、双指针、字符串本质、哈希表、排序二分、动态规划和经典题型，既讲原理，也带你动手写代码，最终建立起属于自己的算法面试方法论。

岗位关联

对 AI 从业者来说，数组与字符串是算法面试的必考地基，也是数据处理、文本 NLP、检索系统里最常用的数据结构——掌握它们，你就拿到了大厂面试的第一张入场券。

目录
  1. 可视化演示
  2. 数组基础
  3. 双指针技巧
  4. 字符串本质
  5. 哈希表法
  6. 排序与二分
  7. 动态规划
  8. 高频题型
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示数组随机访问O(1)、双指针对撞优化、滑动窗口伸缩及KMP前缀匹配四大面试高频技巧，交互切换深入理解算法原理。

本节配有交互动效（进入视口后自动加载，约 3KB）。

随机访问：O(1)内存寻址 数组元素连续存放，通过基地址+偏移量直接计算地址 addr[i] = base + i × sizeof(elem) 无需遍历即可直达任意元素。

数组基础

后台西墙那排储物柜从 0 开始编号，一个挨一个，柜门永远一样宽。你只要听到“7 号柜”，脚都不用挪就能报出里面放的什么道具——这正是数组最骄傲的本事：随机访问。面试里一提到“按下标取东西”，你脑子里就该浮现这排编号柜子。

在计算机里，数组就是一段连续的内存“柜位”。因为每个元素大小相同且紧挨着，系统不需要翻箱倒柜，直接算一笔账就能定位：第 i 个元素住在“起点地址 + i × 单个格宽”的地址上。这笔账里只有一次乘法和一次加法，跟数组多长完全无关。

所以按下标访问永远是常数时间 O(1)。但代价藏在“往中间塞东西”：要在 3 号和 4 号柜之间插新道具，4 号及以后所有柜子都得向右挪一格，属于 O(n) 的搬移操作。好在动态数组（比如 Python 的 list）会在装不下时把柜子数量翻倍重建，把“搬家”成本摊到每一次插入上，均摊下来仍然是 O(1)。

面试中但凡听到“按下标取元素”，你要立刻想到储物柜编号，这是数组最耀眼的勋章；但听到“往中间插一个”或“删掉中间的”，就该意识到整排柜子要咔嗒咔嗒地挪位了——这正是数组增删 O(n) 代价的直觉来源。

addr(a[i])=base+i×size\displaystyle \text{addr}(a[i]) = \text{base} + i \times \text{size}
通俗说明：找到数组第 i 个元素的地址，只需一次乘法和一次加法，所以随机访问是 O(1) 的常数时间。
  1. 起点地址 base数组在内存中第一个柜格的地址，相当于储物柜的 0 号位。
    base\text{base}
  2. 格宽 size每个元素占用的字节数，好比每个柜子都一样宽。
    size\text{size}
  3. 偏移量 i × size从起点走 i 个格宽，精确落在第 i 个元素上。
    i×sizei \times \text{size}
  4. 相加得地址起点加偏移，一步定位，整个计算与 n 无关。
    base+i×size\text{base} + i \times \text{size}

双指针技巧

总监要在道具柜里找一对加起来正好 23 斤的哑铃。笨办法是每拿一个就跟后面所有哑铃称一遍，O(n²) 的功夫。聪明的总监叫来两个场务：一个从最左往右走，一个从最右往左走，每次只看两人手边这对，像一扇缓缓关上的门。

前提是哑铃按重量排好了序。两人手边的和小于目标，说明整个右半场的搭档都不可能更小，只能让左边场务往右换个更重的；和大于目标，就让右边场务往左。两人相向而行，每轮至少有一位前进，最多走 n 步就收工——这就是“对撞指针”。

因为每轮指针至少移动一步，整个流程最多移动 n 步，时间复杂度 O(n)、空间 O(1)。同一思想还能衍生出快慢指针（判断链表成环、数组去重）和滑动窗口（无重复字符最长子串）。滑动窗口本质是“同向双指针”：右指针扩张把新字符请进门，左指针收缩把重复字符请出去，窗口始终保持合法。

“关门的场景”一旦印进脑子里，很多题就通了：有序数组两数之和、判断回文字符串、原地去重，全是两个场务在柜列两侧相向而行的小把戏。面试时看到“有序”两个字，先想想能不能请出这扇“门”。

a[l]+a[r]<T⇒l←l+1;a[l]+a[r]>T⇒r←r−1\displaystyle a[l] + a[r] < T \Rightarrow l \gets l+1;\qquad a[l] + a[r] > T \Rightarrow r \gets r-1
通俗说明：对撞指针的每一步都让“和”单调变化，两人最多各走 n 步，因此整体是 O(n)。
  1. 左指针 l 起步从最左侧出发，整个过程中只会向右移动。
    ll
  2. 右指针 r 起步从最右侧出发，整个过程中只会向左移动。
    rr
  3. 比较和与目标和偏小则左指针右移让和变大，和偏大则右指针左移让和变小。
    a[l]+a[r]<T⇒l←l+1a[l] + a[r] < T \Rightarrow l \gets l+1
  4. 相遇即终止两指针相遇还没命中，说明不存在这样的数对。
    l≥rl \ge r

字符串本质

后台道具间挂着演员的珍珠名牌，每颗珍珠烙一个字，用丝线串好。名牌一旦串成，就不能单独换中间那颗珍珠——必须解开整条链子重穿。字符串正是这样的“珠串”：在 Python 和 Java 里，它是不可变对象，任何“修改”都是新穿一条链子。

字符串底层其实就是字符数组——一颗颗珍珠排成一排；但对使用者来说它“只读”。你没法直接写 s[0] = 'a'（Python 会抛 TypeError），想改只能构造新串。这个特性带来一个著名陷阱：在循环里反复做 s += c，每次都在重新串整条链子。

长度从 1 到 n 的串各复制一遍，总代价是 1 + 2 + … + n，变成 O(n²) 的灾难。正确做法是先把碎片收进列表，最后用 ''.join() 一次穿好，或者用 StringBuilder。另外面试常问编码：ASCII 一个字节存英文字符，UTF-8 用多个字节存中文，处理“字符”与“字节”时要分清边界。

面试官问“字符串拼接性能”时，你只要想到“重穿珠串”就明白为什么 join 是正解：一次性把散落的珍珠按顺序穿好，绝不回头。这个编码细节，也是区分“背过八股”和“真懂原理”的试金石。

T(n)=∑k=1nO(k)=O(n2)\displaystyle T(n) = \sum_{k=1}^{n} O(k) = O(n^2)
通俗说明：每拼接一次就要复制整条珠串，拼 n 次等于把 1 到 n 全部加一遍，变成平方级灾难。
  1. 第 k 次拼接成本 O(k)串的前面已有 k 颗珍珠，全部重穿一遍。
    O(k)O(k)
  2. 累加所有拼接1 + 2 + … + n 次珍珠搬运。
    ∑k=1nk\sum_{k=1}^{n} k
  3. 和为平方级等差数列求和约等于 n²/2。
    n(n+1)2⇒O(n2)\frac{n(n+1)}{2} \Rightarrow O(n^2)

哈希表法

后台门口放着一本登记簿，每件道具的名字对应一个柜号。问“扳手在哪”，翻登记簿一秒答出“12 号柜”。这就是哈希表：一本把“名字 → 柜号”映射起来的万能登记簿。数组靠下标找人，哈希表靠“值”找人，各有各的用武之地。

数组按下标访问是 O(1)，但面试给的往往是“值”而不是下标。哈希表让我们把值当键存进登记簿，之后每次查询都是 O(1)——本质是用额外空间换时间。如同多雇了一位登记员，多占一张桌子，但全场调度速度飞涨。

最经典的例子是两数之和：遍历数组，对每个数 a[i] 算好“缺的伙伴” = T − a[i]，然后去登记簿里查它来过没有。查到了直接返回两个下标，查不到就把当前值登记上。一趟遍历 O(n)，代价是 O(n) 的额外空间。哈希表还能做频次统计（数每个字符出现几次）和去重检测（查“见过吗”）。

有了登记簿，后台调度再也不用满世界翻柜子。面试中看到“找两个数”“有没有出现过”“每个元素出现几次”，优先想想能不能请出哈希表这位登记簿管理员——它总能用一点空间，换回大幅的时间。

complement=T−a[i],hash_lookup(complement)=O(1)\displaystyle \text{complement} = T - a[i], \qquad \text{hash\_lookup}(\text{complement}) = O(1)
通俗说明：对每个元素，只需回答“它的补数之前出现过吗”，用哈希表一次 O(1) 查完。
  1. 求补数目标值减去当前元素，得到要找的“伙伴”。
    T−a[i]T - a[i]
  2. 哈希查找在登记簿里查补数是否出现过，耗时恒定。
    O(1)O(1)
  3. 总时间n 个元素各查一次，整体线性复杂度。
    n×O(1)=O(n)n \times O(1) = O(n)

排序与二分

后台的剧本散落一桌。直接找第 7 场戏得从头翻到尾；总监先把剧本按场次排好，然后每次翻到正中间，看目标在左半还是右半，一下就把范围砍掉一半。这就是“排序预处理 + 二分查找”的组合拳。

很多题数组无序时只能 O(n) 或 O(n²) 穷举；先排个序（O(n log n)），就能享受二分的 O(log n) 查找，或配合对撞指针把两数之和做到 O(n)。代价是排序本身的时间，但当“只查一次却要反复比较”时，这笔买卖非常划算。

二分查找的要点全在边界：while l < r 还是 while l <= r？mid 取左中还是右中？更新是 l = mid + 1 还是 l = mid？背模板不如理解“区间不变量”：每一轮循环，答案一定还在闭区间 [l, r] 里。另一个常考点是归并思想——合并两个有序数组、统计逆序对，都是“切成两半，分别解决，再合并”。

面试遇到“在有序（或可排序）的东西里找目标”，先回忆总监翻剧本的动作：一翻删一半，三翻剩一页。这个直觉比死记边界模板可靠得多，也是你和面试官聊“为什么这样写不越界”时的底气。

mid=⌊l+r2⌋,T(n)=T(n2)+O(1)=O(log⁡n)\displaystyle \text{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor, \qquad T(n) = T\left(\frac{n}{2}\right) + O(1) = O(\log n)
通俗说明：每次比较都让搜索区间减半，所以 n 个数最多 log₂n 次就能定位。
  1. 取中点 mid把当前搜索区间均匀切成两半。
    ⌊l+r2⌋\left\lfloor \frac{l + r}{2} \right\rfloor
  2. 区间减半每轮比较后，搜索范围只剩一半。
    T(n2)T\left(\frac{n}{2}\right)
  3. 对数轮数n 反复除以 2 到达 1，共 log₂n 轮。
    O(log⁡n)O(\log n)

动态规划

想为一场三小时的剧目设计最省时的换景方案。总监的做法是：把整场演出拆成一个个小场景，从第一幕第一场开始，把每个前缀场景的最优结果记在一张“复盘台账”里。后面的场景不重新设计，只看台账里已算好的结果往前推——这就是动态规划。

数组与字符串题里最常见的 DP 是求“最长公共子序列（LCS）”：把两个串各自的前缀当作行和列，dp[i][j] 表示 s 的前 i 个字符与 t 的前 j 个字符能组成的最长公共子序列长度。子问题之间有重叠，台账保证每个子问题只算一次。

状态转移就两条规则：当前字符相等，就从左上角的旧答案加 1；不相等，就取“左边”和“上边”两个旧答案里的较大者。填表方向从左上到右下，最后 dp[m][n] 就是答案。编辑距离（增、删、改各算一次操作）也是同一张表，只是转移时多考虑“替换”。因为填第 i 行只需要第 i-1 行，空间还能优化成两行滚动数组。

台账的好处是“每个子问题只算一次”。面试遇到“最长”“最少次数”“共有多少种”，多半可以像总监一样，把大问题切成小场景，从小往大填表——这比递归加备忘录更好写，也更不容易超时。

dp[i][j]={dp[i−1][j−1]+1,si=tjmax⁡(dp[i−1][j], dp[i][j−1]),si≠tj\displaystyle dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & s_i = t_j \\ \max\big(dp[i-1][j],\, dp[i][j-1]\big), & s_i \ne t_j \end{cases}
通俗说明：字符相等就从斜上角的旧答案加一；不等就抄左边和上边里的较大者。
  1. 初始化空串行任一串为空时，公共子序列长度为 0。
    dp[0][j]=0,dp[i][0]=0dp[0][j] = 0, \quad dp[i][0] = 0
  2. 字符相等则延长尾部字符相同，公共子序列能多包含一个字符。
    dp[i−1][j−1]+1dp[i-1][j-1] + 1
  3. 字符不等取大者只能继承“含 s 不含 t”或“含 t 不含 s”两个旧答案，选较长者。
    max⁡(dp[i−1][j], dp[i][j−1])\max\big(dp[i-1][j],\, dp[i][j-1]\big)
  4. 右下角即答案整张表填完，右下角是最长公共子序列长度。
    dp[m][n]dp[m][n]

高频题型

正式演出前的彩排，总有几个固定节目必须练熟。数组与字符串的面试也一样：两数之和、无重复字符的最长子串、字符串反转、KMP 模式匹配，是出场率最高的四个“必演曲目”。把它们练成肌肉记忆，面试就有了基本盘。

两数之和用哈希表 O(n) 搞定；无重复最长子串用滑动窗口——右指针把新字符伸进来，若遇到重复字符就把左指针跳到重复位置之后；字符串反转就是前后对撞交换，O(n) 且原地完成。这三道题把哈希、双指针、数组交换全部串了起来，堪称“数组三件套”。

最进阶的是 KMP。朴素匹配在失配时主串指针要回退，KMP 的精髓是“主串永不回头”：先预处理模式串，算出前缀函数 π[i]——模式串前 i 个字符里，最长的“既是前缀又是后缀”的长度。失配时直接把模式串滑到可复用前缀的位置，主串指针继续前进，整体做到 O(n+m)。

彩排的意义在于把动作变成肌肉记忆：两数之和找登记簿、最长子串关门滑动、字符串反转前后换手、KMP 主串永不回头。练熟这四首“必演曲目”，你就拥有了自己的后台调度手册，任何变体题都只是换了件道具外衣。

π[i]=max⁡k<i{k:s[0..k−1]=s[i−k+1..i]}\displaystyle \pi[i] = \max_{k < i} \big\{ k : s[0..k-1] = s[i-k+1..i] \big\}
通俗说明：前缀函数记录“已经匹配的部分里有多大一段能直接复用”，让模式串失配时只滑动、不回退。
  1. 前缀后缀相等找模式串前 i 个字符里，最长的真前缀恰好等于同长后缀。
    s[0..k−1]=s[i−k+1..i]s[0..k-1] = s[i-k+1..i]
  2. 取最大长度能复用的最长一段记入前缀函数。
    max⁡k<i{k}\max_{k < i} \{ k \}
  3. 失配即滑动主串指针不动，模式串按 π 滑动后继续匹配。
    O(n+m)O(n + m)

AI 应用场景

API 网关的滑动窗口限流

阶段：模型服务部署与保护（推理服务弹性伸缩）

解决的问题：线上 AI 服务（如大模型对话接口）一旦被突发请求打爆，整个集群都会雪崩。传统固定窗口限流在窗口边界会出现“双倍突发”漏洞。滑动窗口把时间轴切成细粒度格子，每来一个请求就更新窗口两端的指针，像同向双指针一样把窗口内的请求数控制在阈值内，O(1) 时间即可判断放行还是拒绝。

具体案例：某对话机器人上线后，用 1 秒级滑窗加 5 格细分，将峰值 QPS 从超限 300% 稳定压回阈值内，P99 延迟下降 40%，服务不再雪崩。

智能客服的编辑距离纠错

阶段：NLP 文本预处理与语义匹配

解决的问题：用户提问“退换货币流成”时，检索系统匹配不到知识库。传统做法直接丢弃或转人工。编辑距离 DP 给出“最少增删改次数”，把用户输入与知识库每个标题比对，距离小于 2 就判定为错别字并自动纠正——这正是那张“复盘台账”表的直接应用。

具体案例：某电商客服系统接入纠错后，意图识别准确率从 91% 提升到 96%，无效转人工工单减少 30%，用户满意度明显回升。

向量检索中的局部敏感哈希

阶段：召回与近似最近邻搜索

解决的问题：推荐系统要快速找到与当前用户向量最相似的物品向量，暴力两两比对 O(n²) 不可行。工业界用 LSH（局部敏感哈希）把相似向量哈希到同一个桶里，查询时只在该桶内逐一比对——这正是“哈希表把全量查找变成常量级定位”的升级版。

具体案例：某短视频推荐系统利用 LSH 将 1 亿物品池的召回耗时从 200ms 降到 8ms，同时保证召回率不降，线上 A/B 实验点击率提升 5%。

Python 演示

python55 行
def two_sum(nums, target):    seen = {}    for i, num in enumerate(nums):        want = target - num        if want in seen:            return [seen[want], i]        seen[num] = i    return []  def longest_unique_substring(s):    left = 0    last_pos = {}    best = 0    for right, ch in enumerate(s):        if ch in last_pos and last_pos[ch] >= left:            left = last_pos[ch] + 1        last_pos[ch] = right        best = max(best, right - left + 1)    return best  def lcs_length(a, b):    m, n = len(a), len(b)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(1, m + 1):        for j in range(1, n + 1):            if a[i - 1] == b[j - 1]:                dp[i][j] = dp[i - 1][j - 1] + 1            else:                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])    return dp[m][n]  def edit_distance(a, b):    m, n = len(a), len(b)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(m + 1):        dp[i][0] = i    for j in range(n + 1):        dp[0][j] = j    for i in range(1, m + 1):        for j in range(1, n + 1):            if a[i - 1] == b[j - 1]:                dp[i][j] = dp[i - 1][j - 1]            else:                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])    return dp[m][n]  if __name__ == "__main__":    print(two_sum([2, 7, 11, 15], 9))    print(longest_unique_substring("abcabcbb"))    print(lcs_length("abcde", "ace"))    print(edit_distance("horse", "ros"))
目的：一行行实现面试最常考的四个数组与字符串算法——两数之和（哈希表）、无重复字符最长子串（滑动窗口）、最长公共子序列（DP 填表）、编辑距离（DP 变形），覆盖正文全部核心方法。
  1. want = target - num补数：每个元素要找的“伙伴”，对应登记簿的钥匙。
  2. if want in seen:哈希表 O(1) 查询登记簿，查不到就登记当前值。
  3. left = last_pos[ch] + 1滑动窗口收缩：遇到重复字符，左指针直接跳到重复位置之后。
  4. best = max(best, right - left + 1)每轮扩张后更新最长合法窗口长度。
  5. dp[i][j] = dp[i - 1][j - 1] + 1LCS 核心：字符相等时斜上角答案加一。
  6. dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])字符不等时取左边和上边的较大者。
  7. dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])编辑距离三种操作（增、删、改）取最小再加一。

常见误区

误区初学 Python 时试过 `s[0] = 'a'`，看到报错还以为是语法问题。很多人潜意识里把字符串当成字符数组，以为跟 C 语言一样能直接改。

正解Python、Java 的字符串是不可变对象，s[0] = 'a' 会抛 TypeError。任何“修改”都是生成新串。回想珍珠名牌：一旦穿好，想换中间一颗必须重穿整条链子。所以频繁拼接要用 join 或 StringBuilder，否则就是 O(n²) 灾难。

为何常见：C/C++ 的 char 数组可以就地改，跨语言习惯迁移时最容易在这个点上踩坑。

误区觉得二分就是背三个模板之一，`while` 条件写错也不影响“大方向”。

正解二分 90% 的 bug 来自边界：l < r 还是 l <= r 决定循环能否退出；mid 与 l、r 的更新必须保证不变量“答案始终在 [l, r] 内”，否则会死循环或漏答案。正如总监翻剧本，每翻一页都要确信目标还在剩下的半摞里。

为何常见：二分写起来只有几行，看起来简单，但 off-by-one 的 bug 隐藏得很深，简单的测试用例根本发现不了。

误区听说扩容要“搬家”，就觉得每次 append 都是 O(n)，写代码时对动态数组过度担心。

正解动态数组扩容时容量翻倍（1→2→4→8），把搬家成本均摊到每次插入上，均摊时间复杂度是 O(1)。单次 append 偶尔是 O(n)，但 n 次 append 总体是 O(n)。这和储物柜满了就建一排双倍的柜子、把东西平摊进去是一个道理。

为何常见：只盯着单次最坏情况，忽略了“摊还分析”这个关键视角，导致对常用容器的性能产生错误焦虑。

误区两数之和用哈希表一趟搞定，就觉得哈希表万能，永远是“最优解”。

正解哈希表时间 O(n) 但空间 O(n)；排序加对撞指针是 O(n log n) 时间、O(1) 空间。面试官追问“能否不用额外空间”时，双指针才是正解。空间换时间不是白拿的，得像后台多雇一个登记员——快是快了，但得多付一张桌子的租钱。

为何常见：初学者喜欢“无脑快”的解法，忽略题目对空间的要求和面试官递来的引导信号。

误区求无重复最长子串时，先两层循环枚举所有子串再逐一判断，觉得“反正也能过”。

正解那是 O(n²) 的穷举。滑动窗口用右指针扩张、左指针收缩，每个字符最多进出窗口一次，整体 O(n)。区别如同“把每段布料都剪下来量一遍”对比“拿卷尺从头扫到尾”，省下的远不止一半时间。

为何常见：暴力解最先出现在脑海里，缺乏对“指针是否回头”的敏感性——一旦意识到左指针永不回头，O(n) 的解法自然浮现。

面试题

Q1. 已知数组按下标访问，时间复杂度是多少？

单选题 · easy

  • A.O(1)，与数组长度无关← 正确答案
  • B.O(logn)，随长度缩小
  • C.O(n)，随长度线性
  • D.O(n²)，成平方增长

答案：A。数组连续存储，地址公式一次乘加直接定位，恒定时间。B 是二分查找的复杂度，C 是线性扫描，D 是嵌套暴力比较，都与按下标访问无关。

Q2. 在 Python 中执行 s[0] = 'a'（s 是字符串）会？

单选题 · easy

  • A.成功替换首字符
  • B.立即抛 TypeError← 正确答案
  • C.整行被静默忽略
  • D.隐式生成新字符串

答案：B。Python 字符串不可变，像穿好的珍珠名牌不能单换一颗珍珠，赋值会抛 TypeError。生成新串需要通过 s = 'a' + s[1:] 等显式构造完成，而不是下标赋值。

Q3. 二分查找对输入数组的硬性要求是？

单选题 · easy

  • A.数组必须是整数
  • B.数组必须是有序的← 正确答案
  • C.数组不能有重复
  • D.数组必须规模很大

答案：B。二分依赖“比较后能丢掉一半”的单调性，只有有序数组才有这个性质。整数、无重复、大规模都不是硬性条件，二分对无序数组无从下手。

Q4. 用哈希表做两数之和，额外空间复杂度是？

单选题 · mid

  • A.O(1) 常量空间
  • B.O(n) 线性空间← 正确答案
  • C.O(n²) 平方空间
  • D.O(logn) 对数空间

答案：B。哈希表最多要存下 n 个元素，像登记簿要记录每件道具的位置，空间随 n 线性增长。多花 O(n) 空间换来一趟 O(n) 的查找时间，这就是“空间换时间”。

Q5. 字符串 "abcabcbb" 的无重复字符最长子串长度是？

单选题 · mid

  • A.2，最长只有两个字符
  • B.3，最长就是三个字符← 正确答案
  • C.4，最长可达四个字符
  • D.6，最长可达六个字符

答案：B。最长无重复子串是 "abc"，长度 3。滑动窗口让左右指针最多各走 n 步，O(n) 内算出；若两层循环穷举所有子串则是 O(n²)。

Q6. 对撞指针解有序数组两数之和，每轮比较后指针如何移动？

单选题 · mid

  • A.两个指针同时左移
  • B.和偏小则左指针右移← 正确答案
  • C.和偏大则左指针右移
  • D.随机移动其中一个

答案：B。和小于目标时必须让和变大，只能让左指针右移；和大于目标时必须让和变小，只能让右指针左移。这样每轮排除一整片候选，保证 O(n) 且不遗漏。

Q7. “horse“ 变为 ”ros”，编辑距离（增、删、改各算 1 次）是？

单选题 · hard

  • A.两次操作就能完成
  • B.三次操作就能完成← 正确答案
  • C.四次操作就能完成
  • D.五次操作就能完成

答案：B。horse → rorse（替换 h 为 r），→ rose（删掉第二个 r），→ ros（删掉末尾 e），共 3 次。长度差 2 至少需要 2 次删除，且首字符不同还需 1 次替换，少于 3 次不可能。

Q8. 哪些做法能避免字符串循环拼接的 O(n²) 代价？（多选）

多选题 · mid

  • A.列表收集再 join← 正确答案
  • B.使用 StringBuilder← 正确答案
  • C.每次 s += ch 拼接
  • D.字符数组最后转换← 正确答案

答案：ABD。join、StringBuilder、字符数组都是一次性整体组装，代价 O(n)。C 是反复重穿整条珠串，正是要避免的 O(n²) 写法。

Q9. 关于 KMP 算法，正确的说法有？（多选）

多选题 · extreme

  • A.主串指针永不回退← 正确答案
  • B.需要预处理模式串← 正确答案
  • C.最坏时间是 O(n²)
  • D.失配时利用前缀函数← 正确答案

答案：ABD。KMP 的核心是主串不回头，模式串按前缀函数滑动，预处理 O(m) 加匹配 O(n)，整体 O(n+m)。C 的 O(n²) 是朴素匹配的最坏情况，不是 KMP。

Q10. 关于动态数组扩容的说法，正确的有？（多选）

多选题 · hard

  • A.单次插入最坏 O(n)← 正确答案
  • B.n 次插入均摊 O(1)← 正确答案
  • C.容量通常成倍增长← 正确答案
  • D.扩容不消耗任何时间

答案：ABC。容量翻倍使搬家成本均摊到每次插入，均摊 O(1)，但单次触发扩容时要复制所有元素，最坏 O(n)。D 说“不消耗时间”显然错误。这正是“储物柜满了建双排”的摊还分析。