字符串题核心考点：双指针、滑动窗口与KMP底层原理全解析

1. 字符串题到底在考什么先跳出语言 API思维很多人学字符串算法时有个误区一上来就去背reverse()、split()、substring()这些语言内置方法觉得字符串题就是调 API。但刷过《代码随想录》字符串篇的朋友应该都有体会字符串题目表面在考字符串处理实际上考的是底层数组操作、指针移动、边界控制这三件事。因为字符串在绝大多数编程语言里本质就是字符数组所谓算法题无非是让你在不借助高级封装或者在特定限制下完成那些本该内置的操作。比如力扣上那道经典的 344. 反转字符串题目要求不要给另外的数组分配额外空间必须原地修改输入数组。这道题最直接的思路就是双指针左指针指向开头右指针指向结尾交换两个字符然后左指针右移、右指针左移直到两指针相遇。这个解法在 Python 里写出来就四五行在 C 语言里也就多几个临时变量的声明。它考的不是你知不知道reverse()而是你有没有建立字符数组可以按下标访问这个底层意识。再说细一点字符串题的考纲在代码随想录里其实分得很清楚反转类、替换类、匹配类、子串类、去重类。每一类的核心解法背后都对应一种底层思维。反转类对应指针双向移动替换类对应从后往前填充以避免频繁搬移匹配类对应 KMP 的前缀表思想子串类对应滑动窗口去重类对应双指针或哈希统计。你把这些底层模型吃透了语言层面的 API 差异就只是实现细节不再影响你解题。所以这篇文章我想带着大家把字符串篇的骨架搭起来做题时怎么拆解题意、怎么选数据模型、哪些坑高频出现、KMP 到底怎么理解才不玄学。全程用代码随想录的题单思路来讲配合典型题目、易错点和个人实测经验希望你看完能少走我当初走过的弯路。2. 三类高频基础操作反转、替换、拼接里藏着的边界陷阱字符串题目的简单题部分往往不是真的简单而是看起来简单一提交就报错。下面这三类基础操作我逐个拆重点讲它们背后的边界条件和为什么这么写。2.1 反转字符串双指针不是唯一考点边界才是反转字符串是字符串篇的开胃菜但很多人第一次写就挂在边界上。先用最标准的双指针写法void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } }这里的关键是循环条件。用left right而非left right。为什么因为当字符串长度是偶数时比如 4 个字符left 会走到 1、right 走到 2交换后 left2、right1循环自然结束但如果用left2、right1 时还会再进入一次循环交换的是已经处理过的对称区间虽然对结果没影响因为此时 left right下标访问已经越界——不等等越界的情况其实不会在时立即发生因为当 left2、right1 时s[left]和s[right]仍在合法范围内长度为4时下标0-3所以不会报错但逻辑上已经错了当长度为奇数时比如 3 个字符left1、right1 时会走进去交换的是同一个元素无意义。所以总结一句反转字符串用让奇数长度时中间那个字符自然不动偶数长度时正好交换完。但反转类题目的升级版是 541. 反转字符串 II它要求每 2k 个字符反转前 k 个字符。这类题的真正陷阱是剩余字符不足 k 个时怎么处理。我的经验是与其在循环里写一堆 if 判断剩余长度不如把需要反转的区间终点先算出来string reverseStr(string s, int k) { for (int i 0; i s.size(); i 2 * k) { int left i; int right min(i k - 1, (int)s.size() - 1); while (left right) { swap(s[left], s[right]); left; right--; } } return s; }用min(i k - 1, s.size() - 1)一步到位把剩余不足 k 个就全反转和正常反转 k 个两种情况统一了。这个技巧在区间处理题里通用我后面在替换类题目里还会用到。2.2 替换类题目从后往前填充避免反复移动力扣 剑指 Offer 05. 替换空格要求把字符串中的空格替换成%20。最先想到的解法是开一个新字符串遇到空格就追加%20。这种解法在工程上没问题但在算法题里它有额外空间开销。真正贴合底层思维的解法是先扩容再从后往前填充。为什么要从后往前用一个生活类比你在一个装满物品的货架上腾出空间从前往后挪会把后面的物品反复推挤而从后往前腾挪每件物品只需移动一次。字符串也同理先统计空格数量把字符串长度扩展为原长度 空格数 * 2然后两个指针分别指向原字符串末尾和新字符串末尾从后往前逐个复制字符遇到空格就依次填入02%注意是倒序填因为是从后往前。string replaceSpace(string s) { int oldLen s.size(); int spaceCount 0; for (char c : s) { if (c ) spaceCount; } s.resize(oldLen spaceCount * 2); int newLen s.size(); for (int i oldLen - 1, j newLen - 1; i 0; i--) { if (s[i] ! ) { s[j--] s[i]; } else { s[j--] 0; s[j--] 2; s[j--] %; } } return s; }这里我踩过的一个坑是resize之后直接拿s[i]去判断导致逻辑混乱。正确做法是i指向旧字符串末尾j指向新字符串末尾但s本身已经被扩容了所以旧字符仍存在前oldLen个位置里不会被覆盖吗——会因为新字符串的末尾在newLen - 1从后往前时j比i走得快当遇到空格时j一次减 3所以填充的位置永远不会覆盖i还没处理到的旧字符。这个从后往前的妙处就在这。2.3 拼接与分割注意语言的赋值开销字符串拼接看似简单但很多人没意识到在不可变字符串的语言里Java、Python、C#每次拼接都会生成新字符串对象。比如s s a如果放在循环里执行 N 次时间复杂度是 O(N²)。这就是为什么 Java 里建议用StringBuilderPython 里推荐用join。在算法题里如果题目要求拼接字符串我建议优先考虑用字符数组代替字符串拼接。比如 151. 反转字符串中的单词一种解法是先整体反转再逐个单词反转。这个过程中如果频繁用s.substr切片再拼接逻辑容易乱性能也差。我当时自己实现时是先把字符串转成 char 数组先反转整个数组再通过跳过空格、识别单词、反转单词、重新放置四个步骤完成。核心代码如下// 去除多余空格并反转单词的简化版思路 // 1. 双指针去除多余空格快慢指针 int slow 0; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast s.size() s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow); // 2. 整体反转 reverse(s.begin(), s.end()); // 3. 逐个单词反转 for (int i 0; i s.size(); i) { int j i; while (j s.size() s[j] ! ) j; reverse(s.begin() i, s.begin() j); i j; }第 3 步里i j后外层循环会执行i所以i会跳到空格后的第一个字符正好进入下一个单词处理。这一步如果不小心写成i j - 1就会死循环我排查了整整十分钟才反应过来。3. KMP 算法从next 数组到底在存什么到如何手撕实现3.1 为什么暴力匹配会慢无意义的重复比较学 KMP 之前得先理解暴力匹配为什么慢。假设主串是aabaabaaf模式串是aabaaf。暴力做法是主串从第 0 位开始匹配失配后主串回到第 1 位模式串回到第 0 位重新匹配。问题在于主串的第 1 位到第 3 位aba已经被比较过了而且我们知道它们不可能是匹配的起点因为模式串开头是aa这些重复比较就是浪费。KMP 的核心思想是失配时模式串不回退到开头而是回退到已经匹配部分的前缀能对齐的位置。这个位置就是 next 数组也叫前缀表存的东西。3.2 前缀表到底在存什么最长相等前后缀一句话解释next[i] 表示模式串中以 i 结尾的子串里最长的相等前缀和后缀的长度且这个长度小于等于 i1通常小于 i1。用aabaaf举例子串a前缀集合为空后缀集合为空最长相等前后缀长度为 0子串aa前缀a后缀a最长相等长度为 1子串aab前缀a,aa后缀b,ab没有相等长度为 0子串aaba前缀a,aa,aab后缀a,ba,aba最长相等为 1都是a子串aabaa最长相等为 2前缀aa和后缀aa子串aabaaf前缀a,aa,aab,aaba,aabaa后缀f,af,aaf,baaf,abaaf没有相等长度为 0所以aabaaf的 next 数组是[0, 1, 0, 1, 2, 0]。那失配时怎么用这个表假设主串aabaabaaf与模式串匹配到模式串下标 5字符f时失配模式串前 5 个字符aabaa已经匹配成功。aabaa的最长相等前后缀是 2aa说明主串中刚才匹配成功的部分其末尾的两个字符aa已经和模式串开头的两个字符aa对齐。所以模式串直接跳到下标 2 的位置继续匹配主串不需要回退。这就是 KMP 省时间的关键。3.3 手撕 next 数组的代码实现求 next 数组本身就是一个双指针过程void getNext(vectorint next, const string s) { int j 0; next[0] 0; for (int i 1; i s.size(); i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; } if (s[i] s[j]) j; next[i] j; } }这里的核心逻辑是j始终表示当前最长相等前后缀的长度也隐含指向前缀的下一个待比较字符。当s[i] s[j]时长度加一不等时j回退到next[j - 1]这个回退其实就是后缀的某个后缀和前缀的某个前缀重新对齐。我在学习这段代码时花了很久才适应j next[j - 1]这个回退。后来找到一个直观理解想象一个文本编辑器里的撤销操作当后缀扩展失败时你不能把整个匹配进度清零而是回到上次成功匹配的最长可继承前缀处。next[j - 1]就是那个位置。3.4 匹配过程掌握了 next 就从暴力里解放出来得到 next 数组后匹配就顺理成章int strStr(string haystack, string needle) { if (needle.empty()) return 0; vectorint next(needle.size()); getNext(next, needle); int j 0; for (int i 0; i haystack.size(); i) { while (j 0 haystack[i] ! needle[j]) { j next[j - 1]; } if (haystack[i] needle[j]) j; if (j needle.size()) { return i - needle.size() 1; } } return -1; }我总结了一个自查清单KMP 相关代码写完一定要检查这三点next 数组是否用next[j - 1]而不是next[j]回退匹配循环里主串下标i是否始终不回退这是 KMP 的招牌返回起始位置时是否减去了needle.size() - 1。4. 经典字符串题逐题拆解从重复子串到字符串转数字4.1 重复子串判断KMP 的一个巧妙应用力扣 459. 重复的子字符串判断一个字符串是否由它的一个子串重复多次构成。比如abab由ab重复两次构成abcabcabc由abc重复三次构成。常规思路是枚举可能的子串长度但用 KMP 有更优雅的做法。结论是如果字符串 s 由重复子串构成那么 s 的最长相等前后缀长度必须满足s.size() % (s.size() - next[s.size() - 1]) 0。这个结论怎么理解以ababab为例它的 next 数组末尾值是 4最长相等前后缀是abab。那么s.size() - 4 2这个 2 恰好就是重复子串ab的长度。为什么因为当一个字符串由某个子串重复构成时它的最长相等前后缀必然是去掉一个重复子串后的前缀和去掉一个重复子串后的后缀两者相等。用数学语言说如果 s 的长度是 n重复子串长度是 p那么最长相等前后缀长度是 n-p。所以判断条件就是n % (n - next[n-1]) 0。但这里有一个边界next 数组末尾值如果是 0n - 0 nn % n 0恒成立那岂不是所有字符串都满足所以必须额外判断next[n - 1] ! 0bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n); getNext(next, s); int len next[n - 1]; if (len 0) return false; return n % (n - len) 0; }这个题我第一次做时漏掉了len 0的判断结果把所有字符串都判定为 true排查了半天才意识到问题。4.2 字符串转数字与数字转字符串溢出和非法输入的攻防战热搜词里频繁出现字符串转数字递归法将一个整数 n 转换成字符串说明这是很多人的痛点。力扣 8. 字符串转换整数 (atoi) 是一个极其考验细节的题。先讲数字转字符串的经典递归写法void intToString(int n, string res) { if (n 10) { res.push_back(n 0); return; } intToString(n / 10, res); res.push_back(n % 10 0); }递归思路很简单先处理高位n/10再处理当前位n%10。因为递归是先递后归所以高位会先被写入字符串。这里有个细节n 0是把整数转成字符的标准做法因为 ASCII 码中0到9是连续的。再讲 atoi 的完整实现。这道题的坑点清单能列一长串前导空格、正负号、非数字字符、溢出、空字符串。我的解法分四步走int myAtoi(string s) { int i 0; int n s.size(); // 1. 跳过前导空格 while (i n s[i] ) i; // 2. 处理正负号 int sign 1; if (i n (s[i] || s[i] -)) { if (s[i] -) sign -1; i; } // 3. 读入数字并处理溢出 long long res 0; while (i n isdigit(s[i])) { res res * 10 (s[i] - 0); if (sign 1 res INT_MAX) return INT_MAX; if (sign -1 res (long long)INT_MAX 1) return INT_MIN; i; } return sign * res; }这里最关键的溢出处理我是用long long做中间变量每加一位就检查是否超过INT_MAX正数情况或INT_MAX 1负数情况因为负数的最小值绝对值比正数最大值大 1。4.3 反转字符串中的单词状态机思维解决空格处理前面提到过 151 题的思路这里补充一个容易忽略的点如何处理字符串开头的空格、结尾的空格、以及单词之间多个空格用快慢指针 状态位的方式最清晰。string reverseWords(string s) { // 第一步清洗字符串去掉多余空格 int slow 0; bool inWord false; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (!inWord) { if (slow ! 0) s[slow] ; // 单词之间加一个空格 inWord true; } s[slow] s[fast]; } else { inWord false; } } s.resize(slow); // 第二步整体反转 reverse(s.begin(), s.end()); // 第三步逐个单词反转 int start 0; for (int end 0; end s.size(); end) { if (end s.size() || s[end] ) { reverse(s.begin() start, s.begin() end); start end 1; } } return s; }inWord这个布尔变量本质是一个状态机false表示当前不在单词内遇到非空格字符时进入单词状态true表示在单词内连续的非空格字符直接复制。这一步解决了所有多余空格问题。第三步反转单词时注意用了end s.size()而不是end s.size()这是为了在遍历到字符串末尾时也能触发一次反转最后一个单词后面没有空格。5. 字符串题的记忆化模板双指针、滑动窗口、哈希表如何选型5.1 三类字符串题型的特征识别字符串题虽然多但解法套路是有迹可循的。我根据自己的刷题经验整理了一个粗略的分类题型特征典型题目首选解法时间复杂度要求原地修改字符数组反转字符串、替换空格双指针/从后往前填充O(n)找子串、求子串满足某种性质无重复字符的最长子串滑动窗口O(n)判断字符是否出现过、计数有效字母异位词、找第一个唯一字符哈希表/数组计数O(n)查找子串位置实现 strStr()KMPO(n)判断循环构成重复的子字符串KMP 变体O(n)具体说看到原地修改基本是双指针看到最长子串窗口内满足条件基本是滑动窗口看到是否含重复字符出现次数基本是哈希表或固定大小数组。哈希表统计字符频次时有一个常见优化如果字符集是确定的比如只包含小写字母可以直接用int count[26] {0}代替unordered_map省去哈希计算的开销。这个优化在竞赛和面试白板编程中都很加分。5.2 滑动窗口的通用框架大多数子串题的答案滑动窗口解决的就是连续子串类问题。我在代码随想录里学到最实用的框架是这样的int slidingWindow(string s) { int left 0, right 0; unordered_mapchar, int window; int res 0; while (right s.size()) { char c s[right]; window[c]; right; // 当窗口不满足条件时移动 left 收缩窗口 while (/* 窗口需要收缩的条件 */) { char d s[left]; window[d]--; left; } // 此时窗口满足条件更新结果 res max(res, right - left); } return res; }以无重复字符的最长子串为例收缩条件是窗口内某个字符出现次数大于 1。这个框架的好处是把扩展窗口和收缩窗口分离你只需要关注两件事什么时候扩展每次右指针移动、什么时候收缩满足什么条件时需要左指针移动。几乎所有子串类题目——最小覆盖子串、找到字符串中所有字母异位词、滑动窗口最大值这个用单调队列——都能套这个模板。5.3 为什么用数组计数而不是哈希表两个实操案例当字符集是 ASCII 码128 个字符或小写字母26 个字符时数组计数是更优选择。力扣 242. 有效的字母异位词标准解法就是用长度为 26 的数组分别统计两个字符串中每个字母出现的次数然后比对。bool isAnagram(string s, string t) { if (s.size() ! t.size()) return false; int count[26] {0}; for (char c : s) count[c - a]; for (char c : t) { count[c - a]--; if (count[c - a] 0) return false; } return true; }第二遍遍历 t 时边减边检查一旦某个字母的计数变成负数说明 t 中该字母比 s 多直接返回 false。比先减完再统一检查更早退出。类似的还有字符串中的第一个唯一字符用一个vectorint存 26 个计数第一遍统计第二遍找第一个计数为 1 的下标。这类题用数组计数的另一个好处是代码可读性高面试官一眼能看出你的思路。6. 刷题路上的高频踩坑实录来自真实提交的教训6.1 越界访问循环终止条件的差一错误字符串题目里最隐蔽的 bug 是数组越界而越界往往不是明显越界而是最后一轮循环越界。比如反转单词的第三步如果你写for (int end 0; end s.size(); end)当 end 到达最后一个字符但仍不是空格即最后一个单词没有后缀空格时永远不会触发反转逻辑。解决办法就是我前面代码里写的end s.size()在 end 等于 size 时做一次收尾处理此时reverse(s.begin() start, s.begin() end)中的end等于 size正好指向末尾的下一个位置reverse 的半开区间[start, size)刚好覆盖最后一个单词。6.2 字符类型判断isdigit 和 0-9 的区别字符串转数字时有的人习惯用c 0 c 9有的人用isdigit(c)。两者在绝大多数情况下等价但有一个区别isdigit是 C 标准库函数需要包含头文件如果你用的是ctype.h或cctype某些实现里isdigit的参数要求是非负整数EOF 除外如果传char类型且该字符的 ASCII 值大于 127比如扩展字符在不同编译器下可能是未定义行为。稳妥起见刷算法题时用c 0 c 9更可控。6.3 字符串长度变化的坑resize 后别再用旧长度遍历替换空格那种题目resize之后字符串长度变了。如果你在 resize 之前保存了旧长度遍历时混用新旧长度最常见的 bug 是该处理的字符没处理或者数组访问越界。我的建议是扩容后立即用新长度初始化尾指针旧长度只用于遍历旧字符串内容。在代码里明确用两个变量名区分oldLen和newLen不要都用n。6.4 C 中 string 的 size() 返回值类型unsigned 的隐式转换string::size()返回size_t是 unsigned 类型。如果你写for (int i 0; i s.size() - 1; i)而s.size()是 0那么s.size() - 1会变成一个巨大的正数无符号整数的回绕循环会执行大量无效甚至越界的操作。这在处理空字符串时尤其危险。我个人的习惯是在需要用到s.size()做算术运算时先显式转成 intint n (int)s.size();然后用 n 操作从源头规避无符号问题。6.5 反转区间别搞混C reverse 是左闭右开C 的reverse(first, last)反转的是[first, last)区间不包含 last。所以reverse(s.begin(), s.begin() k)反转的是前 k 个字符如果你想反转下标 [start, end]要写reverse(s.begin() start, s.begin() end 1)。这类左闭右开的区间约定在很多 STL 函数中都适用一旦记混就会差一位。我见过不少人在做 541 题时因为min(i k - 1, s.size() - 1)的终点没加 1 导致反转范围少了一个字符。7. 从刷题到实战字符串算法在真实项目里的延伸思考很多人会问刷字符串算法题到底有没有用我的回答是如果你只是想通过面试刷题就是必要的敲门砖如果你想写出健壮的代码刷题过程中养成的边界意识会直接迁移到日常开发里。举个真实的例子。我之前在处理一个日志解析模块时需要从一个超长字符串中提取两只指定的子串之间的内容。我先想到用find加substr硬切后来发现主串长度大、需要提取的子串数量多而且子串之间存在重叠直接调 API 代码里全是魔法数维护起来非常痛苦。后来我意识到这本质上就是一个多模式串匹配的变形用 KMP 的思路先把每个模式串的 next 数组算好再一遍扫描主串把所有匹配位置记下来最后统一切分。性能从原来的 O(n×m) 降到 O(nm)代码的可读性也好很多。再比如字符串反转的逻辑看起来只能在算法题里见到但我在处理一个问题时确实用到过导出数据时列的顺序是反的我不想改底层的查询就在导出层把列名反转。这种需求虽然简单但如果你清楚反转区间和局部反转的组合技巧可以一条语句就搞定。所以我的建议是不要用实用主义去评判算法题的价值。字符串算法训练的是你对数据在内存里怎么组织操作的代价是什么的直觉。这种直觉在某些人眼里不值钱但等你在生产环境里面对一个性能瓶颈时它会从潜意识里浮出来。8. 复盘与提速字符串篇的高效刷题姿势最后分享一个具体的刷题计划建议。字符串篇我自己的刷题路径是基础操作热身2~3 天完成反转字符串、反转字符串 II、替换空格、反转字符串中的单词、左旋转字符串。重点是吃透双指针的边界条件。KMP 专项突破3~4 天先用 28. 找出字符串中第一个匹配项的下标即 strStr练手再攻 459. 重复的子字符串。KMP 一定不能只看不写要手推 next 数组至少三个例子。综合应用巩固2~3 天做字符串转整数、最长公共前缀、有效字母异位词、无重复字符的最长子串梳理滑动窗口和哈希计数的模板。刷的过程中我强烈建议每道题在 AC 之后写一个一刷复盘这题的核心考点是什么第一次提交错在哪里有没有可以用到下一题的通法我在刷完字符串篇后把总结浓缩成了三条心法双指针管反转滑动窗口管子串前缀表管匹配。这三句话基本覆盖了字符串篇 80% 的题型。至于背模板还是理解模板的问题我的态度是模板要背但不能只背。背的作用是减少思考负担让你在写代码时不必现场推演边界。但模板背后的原理必须吃透因为面试时考官经常会追问如果字符串里还有换行符怎么办如果是多字节字符呢如果内存不够用呢。这时候只有理解了原理你才能灵活调整模板。字符串篇和链表篇、二叉树篇最大的不同在于字符串题目的载体是编程语言内置的字符串类型不同语言的 API 差异会带来完全不同的实现思路。我见过用 Python 写反转单词三行搞定用 C 写同样的题需要四五步。但这不意味着 Python 更简单而是 C 逼你更接近底层。如果你想真正理解字符串处理C 是不错的练习语言如果你主要用 Python 面试也要会解释 Python 内置方法的时间复杂度。这条刷题路径走下来字符串相关的题目基本能形成肌肉记忆。之后再遇到新题你会自然而然地先分析这是什么类型的操作再套对应的模板最后结合边界条件做调整。这也是我从代码随想录的字符串篇里获得的最大收益。