一、题目是什么先看懂 466 在考什么1.1 原题拆解子串和子序列是两回事LeetCode 466 这道题表面看是字符串实际考的是子序列匹配。题目里定义了一个记号[s1, n1]表示把字符串 s1 重复 n1 次得到的超长字符串[s2, n2]同理。你的任务是返回一个最大整数 m使得[s2, m]是[s1, n1]的子序列。方法签名固定为public int getMaxRepetitions(String s1, int n1, String s2, int n2)这里最关键的一点是题目要的是子序列不是子串。很多人一上来就理解成子串然后整个人就被绕进去了。子串要求连续出现在大串里比如说 s1abn12大串是 abab“ba” 不是它的子串因为不连续。但子序列只要求按顺序出现中间能不能跳过去都无所谓。还是拿 abab 举例“bb” 不是子序列不是因为第二个 b 出现在第一个 b 之后但没有两个 b 能按顺序出现实际上 abab 里只有两个 b位置是 1 和 3按顺序取第二个 b 需要先有一个 b 在它前面也就是位置 1 的 b取完后位置 3 的 b 还在所以 b 不够。这种理解一旦出错后面完全没法做。再举一个有代表性的例子s1abn13大串是 abababs2abn21。因为 ab 就是大串的子串所以它能匹配 3 次返回 3。但如果 s2ban21“ba” 并不是 ab 的子串可它仍然不是子序列注意 ababab 里有没有一个 a 出现在某个 b 之后没有因为 a 永远在 b 后面所以 ba 无法按顺序匹配结果仍然是 0。这个例子能同时说明子串与子序列的差别面试时用来给面试官讲思路很合适。很多 Java 工程师看到这个题的第一反应是StringBuilder把字符串拼出来然后用indexOf或者双指针去数。这个方法在小数据量下完全能跑可是题目里 n1 最大可以到 10^6s1 长度可以到 100老老实实拼接出来的字符串长度超过 10^8直接内存溢出。就算不拼接用循环去模拟 10^8 次扫描在 LeetCode 的时限下也基本超时。所以这道题真正要解决的不是“怎么匹配”而是“怎么把匹配次数快速算出来”。1.2 暴力解法能过样例过不了极限数据先把暴力解法写出来你会更容易理解后面优化到底优化了什么。暴力思路很直接把 s1 重复 n1 次当成一个极长的输入流用一个指针遍历它再用另一个指针在 s2 上移动匹配上就前进匹配完一个 s2 就计数加一。为了避免真的拼接出超长字符串用取模模拟重复即可。public int bruteForce(String s1, int n1, String s2, int n2) { int len1 s1.length(), len2 s2.length(); int p 0; int count 0; for (int i 0; i len1 * n1; i) { if (s1.charAt(i % len1) s2.charAt(p)) { p; if (p len2) { p 0; count; } } } return count / n2; }这段代码能跑但有两个隐患。第一个是明显的性能问题外层循环是len1 * n1极限情况下是 10^8 次Java 里一般会超时。第二个是更隐蔽的溢出问题len1 * n1本身的乘法结果可能超过 int 上限虽然题面约束不一定卡这点但写工程化代码时应该尽量避免这种隐患。暴力解法的本质是逐字符扫描它的问题是没法跳过已经重复过的部分。比如 s1abn110000s2a这种情况下我明明知道每个 s1 块都能匹配一个 a扫 10000 次纯属浪费时间。所以下一步的核心思路就是找到这种“规律”把大量重复直接算出结果。二、周期检测从 O(n1 * len1) 降到 O(len1 * len2)2.1 匹配完成后真正值得记录的三个状态先把“扫描一个 s1 块”这件事单独拎出来看。我把 s1 完整扫一遍为了描述方便叫它“一个块”。每扫描完一个块我需要知道三件事已经消耗了多少个 s1、已经完整匹配了多少个 s2、当前 s2 指针停在哪个字符上。这三者才是匹配过程的完整状态。我在第一次做这题时很容易犯一个错只记录匹配了多少个 s2不记录指针位置。但指针位置才是关键。举例来说如果 s1abs2ab扫描完一个 s1 块后s2 指针必定回到开头如果 s1abs2ba扫完一个 s1 块后s2 指针可能停在某个中间位置。同样的 s1 块从不同的指针位置开始扫描得到的匹配数完全不同。所以状态必须包含指针位置。接下来的观察是s2 的长度是有限的指针位置 p 只可能是 0 到 len2 - 1 之间的整数。根据鸽笼原理如果我们连续扫描足够多的 s1 块总会出现两次扫描后指针停在同一个位置。也就是说不管 s1 和 s2 多奇怪循环节一定存在而且出现次数不会超过 len2 块。这个结论是所有优化成立的地基。2.2 如何把循环节转化成数学计算假设扫描完某个 s1 块后指针 p 停在位置 X这时消耗的 s1 数是 usedS1匹配出的 s2 数是 matched。后来扫描完另一个 s1 块后指针又停在同一个 X此时消耗的 s1 数是 usedS1匹配出的 s2 数是 matched。因为两次状态里指针位置相同而下一个 s1 块是同一个字符串所以接下来发生的一切会完全重复。那么从第一次到第二次之间这段过程就是一个周期一个周期消耗的 s1 块数cycleS1 usedS1 - usedS1一个周期内匹配出的 s2 次数cycleMatched matched - matched现在我们知道了每个周期能匹配多少 s2剩下的事情就非常简单。如果总共有 n1 个 s1 块现在已经用掉了 usedS1 个那么剩余remain n1 - usedS1个块。用整数除法times remain / cycleS1表示我们还能完整跳过多少轮周期。跳过这些周期后可以一次性把 matched 增加times * cycleMatched。剩下的不足一个周期的块数再单独扫一遍。这就是整个算法最核心的数学推导理解到这里代码就只是把思路翻译成 Java。2.3 为什么用 HashMap 而不是其他办法既然要记录“指针位置 p - (usedS1, matched)”这种映射关系最自然的数据结构就是HashMapInteger, int[]。Java 里用 int[] 作为 value比每次都创建一个自定义对象要轻量读和写都方便。key 只存一个 int 指针 pvalue 存两个计数值简单直接。这里有人会问能不能用数组代替哈希表理论上可以开一个长度为 len2 1 的数组下标就是指针位置。但由于我们还需要知道某个位置“是否已经出现过”用一个 boolean 数组加两个计数数组也能做到。不过 HashMap 的语义更清晰面试时解释周期检测也更自然。Java 的 HashMap 在 key 只有 int 的自动装箱场景下性能足够好完全不用为了性能去手写数组版本。三、Java 实现getMaxRepetitions 的 AC 代码与逐段解读3.1 完整可提交的实现下面这段代码是 LeetCode 466 的标准解法配合上面的周期检测思路能直接 AC。import java.util.HashMap; import java.util.Map; public class LeetCode466 { public int getMaxRepetitions(String s1, int n1, String s2, int n2) { if (n1 0 || n2 0) { return 0; } char[] c1 s1.toCharArray(); char[] c2 s2.toCharArray(); int len1 c1.length; int len2 c2.length; // ps2 中当前匹配到的位置 // matched已经完整匹配出了多少个 s2 // usedS1已经扫描完多少个 s1 int p 0; int matched 0; int usedS1 0; // key扫描完一个 s1 块后 p 的位置 // value[扫描完的 s1 块数, 完整匹配的 s2 次数] MapInteger, int[] visited new HashMap(); while (usedS1 n1) { for (char ch : c1) { if (ch c2[p]) { p; if (p len2) { p 0; matched; } } } usedS1; if (!visited.containsKey(p)) { visited.put(p, new int[]{usedS1, matched}); continue; } int[] pre visited.get(p); int cycleS1 usedS1 - pre[0]; int cycleMatched matched - pre[1]; int remain n1 - usedS1; int times remain / cycleS1; usedS1 times * cycleS1; matched times * cycleMatched; if (usedS1 n1) { break; } // 周期跳过之后剩余部分不足一个周期清掉历史状态 // 防止旧状态干扰剩余模拟 visited.clear(); visited.put(p, new int[]{usedS1, matched}); } return matched / n2; } }这个版本我在本地跑了多组边界数据包括 s2 长度 1、s1 与 s2 完全无法匹配、n1 接近上限等场景结果都稳定。接下来拆开讲每一段为什么这么写。3.2 代码关键步骤逐段解读第一块是转字符数组和初始化。很多人写这类题习惯用s1.charAt(i)性能没问题但反复调用length()会增加代码噪音。转成char[]后内层循环直接对数组遍历语义更干净。len2单独存出来是为了在 p 达到末尾时能快速和数组长度比较。内层 for 循环是真正的匹配器只有当前字符恰好等于 s2 期待的那个字符p 才前进。这完全对应子序列的定义中间跳过的字符一概不管。如果 p 前进到了 len2说明一个完整的 s2 已经匹配完这时候把 p 归零matched 加一。注意这里不能直接 p 然后继续循环否则会数组越界。外层 while 循环每次处理完一个完整的 s1 块后usedS1 加一。此时分两种情况处理。如果当前指针 p 是个从未见过的位置说明没有周期可跳就把当前状态存进 visited 并进入下一块。如果 p 之前见过说明发现了一个周期按照第 2 章推导出的公式计算 cycleS1 和 cycleMatched然后用整数除法算出 times把这两组数字一次性推进。有个细节值得专门提一下跳完周期之后我清空了 visited 再重新插入当前状态。这样做的原因是周期跳跃之后剩余块数已经不足一个完整周期历史状态里记录的数字和当前状态距离太远如果不清空后续极小的剩余部分也有可能再次触发旧的跳跃虽然结果大概率还是对但逻辑不干净容易让面试官怀疑边界处理能力。清空之后再重新累积剩余部分至多再出现 len2 个新状态复杂度完全可控。3.3 为什么最后要返回 matched / n2这是新手最容易写错的地方。matched 表示“成功匹配出的单个 s2 字符串次数”而不是最终要求的 m。题目要求的是[s2, m]是[s1, n1]的子序列也就是 s2 重复 m 次得到的大串。一个[s2, n2]等于把 s2 重复 n2 次里面包含 n2 个单独的 s2。所以如果我们匹配出了 matched 个单独的 s2最终能组成多少个[s2, n2]就是 matched 除以 n2。举个直观的例子s2abn22那么[s2, n2]就是 abab。如果大串里能匹配出 5 次独立的 ab那么最多只能组成 2 个 abab5 / 2 2余下那个单独的 ab 不够凑成第二个完整的 [s2, n2]。程序返回整数 m所以这里的除法是整数除法自动向下取整。四、边界条件与细节打磨4.1 极端输入测试拿到这道题第一个要处理的边界就是 n1 和 n2 等于 0 的情况。n10 时[s1, n1]是空串任何非空子序列都不可能匹配直接返回 0。n20 时[s2, n2]是空串空串是任何字符串的子序列理论上任意 m 都可以但 LeetCode 要求返回 int遇到这种情况我选择直接返回 0这也是多数题解采用的安全约定。虽然 LeetCode 的测试用例大概率不会覆盖 n20但工程上必须考虑。另一个常见边界是 s2 中包含 s1 完全没有的字符。比如 s1abcs2xn1 再大也不可能有匹配结果。这种场景下内层循环永远匹配不到 xp 一直停在 0matched 永远是 0程序最后返回 0。代码不仅能跑而且不会死循环因为 usedS1 一直在增加外层 while 一定会结束。当 len21 时情况比较简单但有个容易出错的点每次匹配到该字符p 立刻从 0 变到 1然后因为 p len2 又归零。这一瞬间的加一和取模一定要放在同一个逻辑块里否则可能在同一个字符上多匹配或者少匹配。建议自己用 s1aaan13s2an21 去推一遍得到的结果应该是 3。4.2 整数溢出与取整问题很多人在计算len1 * n1时已经埋下了溢出的隐患。虽然 LeetCode 的 n1 上限是 10^6len1 上限是 100乘起来 10^8 不会超过 int 范围但这是巧合不是设计。我在暴力解法里不直接乘而是用i % len1来模拟重复就是为了不触碰这个乘法。优化解法里全程不计算总长度只根据 usedS1 和 n1 判断结束条件彻底避开了一次性的大乘法。周期跳跃里有两处乘法times * cycleS1和times * cycleMatched。times 最大也就是 n1 / cycleS1cycleMatched 最大也不会超过 len1 量级所以最坏情况仍然在 int 范围内。但如果你在改写时用了更宽的题目约束或者想把代码留给未来复用建议把这两个乘法结果声明为 long最后在返回处再转回 int。LeetCode 这个方法签名返回 int不能随意改成 long。matched / n2这一步也要注意除零问题。n20 时不能除所以代码开头必须拦截。这个看起来像废话的细节实际是很多提交 Runtime Error 的源头。4.3 常见误区这里并不适合直接套 KMP有一类同学看到“字符串重复”就条件反射想到 KMP 算法实际上 KMP 解决的是子串匹配要求模板串在主串里连续出现而这道题要的是子序列匹配允许跳字符。把 s1 真实拼接出来再用 KMP 数 s2 出现了几次得到的是子串出现次数不是子序列匹配次数语义完全错位。如果面试官进一步问能不能用 KMP 加速每个 s1 块内部的匹配理论上可以因为每个 s1 块是固定的可以对每个指针位置预处理出块内匹配信息但实现复杂度很高收益在 LeetCode 的数据范围内也不明显。我一般只会在被追问时才提一句“可以做预处理”不会主动把答案往 KMP 上引。真正有效的优化就是周期检测它把 O(n1 * len1) 的暴力降到 O(len1 * len2) 的级别已经是对题目的最优解。五、错误排查与面试扩展5.1 高频错误速查表我在刷这道题的过程中以及后来看别人提交记录时发现有几个错误反复出现。这里整理成一张速查表方便你提交前自查。错误现象根本原因解决办法直接拼接字符串导致内存溢出没有理解 n1 可以到 10^6用取模或周期检测不要真实拼接结果比预期大匹配的是子串而不是子序列确认内层只前进 s2 指针不要求连续p 未归零导致越界p 到达 len2 后没有重置在 p 后立即判断p len2周期判断用 matched 而不是 p没有抓住真正决定状态的是指针位置HashMap 的 key 用 p不要用 matched返回matched 而不是 matched / n2混淆单个 s2 和重复 s2 的含义记住[s2, n2]包含 n2 个 s2n20 时除零缺少边界判断开头if (n1 0 || n2 0) return 0;这六条基本覆盖了我在评论区见过的绝大多数问题。尤其第一条我看着不少标题写着“最暴力解法”的帖子贴出的代码一跑大数据就挂原因就是没有考虑真实拼接的内存成本。5.2 这题值得跑的测试用例如果自己写代码没有把握下面几组用例可以帮你验证实现是否正确。第一组是 s1abn13s2abn21期望 3。第二组是 s1acbn14s2abn22。这里大串是 acbacbacbacbab 可以匹配出 4 次除以 n22期望 2。第三组是 s1aaan13s2aan21期望 4。这个用例能检验重复字符的处理我第一次跑错就是在这种场景下把匹配数数少了。第四组是 s1abn11s2ban21期望 0用来验证子序列语义。第五组是 s1an110s2an23期望 3。这种 len21 的小用例很适合打断点观察 p 的归零过程。把这几组都跑通代码基本就稳了。5.3 面试官可能怎么往深了问这题在 Java 面试里不常直接出现但一旦出现很可能是想考察两件事第一你对子序列和子串的区别是否敏感第二你能不能从重复中识别出循环。如果回答思路能先讲暴力再讲状态记录最后讲周期跳跃面试观感会好很多。常见的追问之一是“如果 s1 和 s2 都特别长比如长度上万位次上万这个解法还成立吗”答案成立复杂度 O(len1 * len2)空间 O(len2)和 n1 基本无关。追问之二是“如果不给你 n1 的上限而是无限重复 s1让你找循环周期怎么办”那就等同于判断状态是否会一直循环实际上就是本题周期检测的极端版本把 while 条件改成不终止再用 map 检测重复即可。追问之三是“如果匹配规则改成子串你会怎么做”这时才轮得到 KMP 或者查字符串算法上场。我个人在实际刷题中的体会是LeetCode 466 最大的价值不在于这道题本身而在于它逼你把“重复”这个概念拆解成状态和周期。凡是遇到循环膨胀类的问题无论是字符串、数组还是时间序列先问一句“状态空间是不是有限”往往就能找到突破口。这道题我正在做的时候也被卡了半天后来在纸上手动模拟了两组状态表彻底理解了 map 里 key 的含义代码就顺手了。面试前想突击循环节类题目466 是性价比很高的一道。