题目背景各位家人们今天咱们来拆解一道算法面试中极其经典的字符串难题[438. 找到字符串中所有字母异位词]。 这道题可以说是“滑动窗口Sliding Window”的教科书级经典应用不仅考察了对窗口边界的掌控力还考察了如何极致压缩时间复杂度。【题目描述】给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。字母异位词指字母相同但排列不同的字符串。【示例】输入:s cbaebabacd, p abc输出:[0,6]解释:起始索引等于 0 的子串是 cba, 它是 abc 的异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。✨ 核心破题逻辑定长滑动窗口 频率数组直觉陷阱每次从s里截取一段跟p一样长的字符串排个序再对比致命后果每一次排序都需要额外时间加上外层循环如果字符串超级长绝对会超时TLE【降维打击定长滑动窗口】我们要找的是异位词说白了就是“字母种类和数量一致不管顺序”。 既然题目说明了“只包含小写字母”我们就可以用两个大小为 26 的数组scount和pcount来当做计数的“备忘录”这比真正的哈希表要快得多破题三步曲打造标尺 (pcount)先把目标字符串p里的字母频率统计出来这是我们的“核对标准”。初始化第一个窗口在s的最左边先吃进一个和p同样长度的窗口统计出scount并和pcount进行第一次核对。窗口开始滑动灵魂操作窗口整体向右平移一格。吃进新字符右边新进来的字母在scount里对应数量1。吐出旧字符左边被移出窗口的字母在scount里对应数量-1。每次滑动只发生这两次简单的加减法操作完全不需要重新扫描整个窗口然后立刻比对scount和pcount。 C 满分 AC 代码掌握了上述逻辑我们来看看优雅的 C 实现。注意代码中的几个防坑细节#include iostream #include vector #include string using namespace std; class Solution { public: vectorint findAnagrams(string s, string p) { // 防坑 1兜底防线如果 s 比 p 还短直接下班防止越界报错 if (s.size() p.size()) { return {}; } // 亮点用数组代替哈希表速度起飞 vectorint scount(26, 0); vectorint pcount(26, 0); vectorint res; // 1. 初始化第一个窗口和目标标尺 for(int i 0; i p.size(); i) { scount[s[i] - a]; pcount[p[i] - a]; } // 第一次核对 if(scount pcount) { res.push_back(0); } // 2. 窗口开始向右滑动 for(int i p.size(); i s.size(); i) { // 吃进右边界的新字符 scount[s[i] - a]; // 吐出左边界外的旧字符 (原来左边界的字符下标是 i - p.size()) scount[s[i - p.size()] - a]--; // 每次滑动后进行核对 if(scount pcount) { res.push_back(i - p.size() 1); } } return res; } }; 硬核原理解析大厂面试加分项如果你能在面试中讲出以下两点面试官绝对会对你刮目相看1. 神奇的s[i] - a是什么意思这其实是利用了底层 ASCII 码的物理特性。 在计算机底层小写字母a到z是按顺序排列的数字97 到 122。 当我们写出s[i] - a时就是用当前的字母减去a如果是a97 - 97 0正好放进 0 号抽屉。如果是b98 - 97 1正好放进 1 号抽屉。以此类推……这个极其巧妙的数学减法让我们省去了构建复杂哈希表的巨大开销2. Cvector的重载运算符在 C 中如果我们比较两个类型相同、大小相等的vector可以直接使用scount pcount。底层会自动帮我们逐个元素进行对比这不仅让代码极其简洁而且由于是定长26个元素的连续内存块对比速度极快 复杂度分析时间复杂度$O(N)$。这里 $N$ 是字符串s的长度。虽然每次循环都要对比两个大小为 26 的数组但 26 是常数级操作相当于 $O(26 \times N)$最终时间复杂度依然是极速的 $O(N)$。全程没有冗余的重复扫描空间复杂度$O(1)$。我们仅仅申请了两个大小固定为 26 的整数数组无论输入字符串有多长消耗的内存空间都不会增加。 总结“定长滑动窗口”的核心就在于那句口诀吃进来一个吐出去一个。只要把控好这个边界再结合ASCII码相减映射到数组的高阶技巧任何同类型的字符串匹配难题都会在你面前迎刃而解附上动画演示!DOCTYPE html html langzh-CN head meta charsetUTF-8 meta nameviewport contentwidthdevice-width, initial-scale1.0 title滑动窗口魔法代码同步演示/title script srchttps://cdn.tailwindcss.com/script style .cell-transition { transition: all 0.3s ease-in-out; } /* 字符方块状态 */ .char-box { border-color: #e5e7eb; background-color: #f9fafb; color: #9ca3af; } .char-in-window { box-shadow: 0 0 10px rgba(59, 130, 246, 0.4); border-color: #3b82f6; background-color: #eff6ff; color: #1e3a8a; transform: scale(1.05); z-index: 5; } .char-add { box-shadow: 0 0 15px rgba(34, 197, 94, 0.7); border-color: #22c55e; background-color: #dcfce7; color: #14532d; transform: scale(1.15); z-index: 10; } .char-remove { box-shadow: 0 0 15px rgba(239, 68, 68, 0.7); border-color: #ef4444; background-color: #fee2e2; color: #7f1d1d; transform: scale(1.15); z-index: 10; opacity: 0.8; } .char-match { box-shadow: 0 0 20px rgba(234, 179, 8, 0.8); border-color: #eab308; background-color: #fef9c3; color: #854d0e; transform: scale(1.1); z-index: 10; font-weight: 900; } /* 频率表动画 */ .freq-match { background-color: #dcfce7 !important; color: #166534; font-weight: bold; } .freq-mismatch { background-color: #fee2e2 !important; color: #991b1b; font-weight: bold; } /* 代码高亮样式 */ .code-line { transition: all 0.2s; border-left: 4px solid transparent; } .code-highlight { background-color: rgba(59, 130, 246, 0.25); border-left-color: #3b82f6; color: #ffffff !important; text-shadow: 0 0 5px rgba(255,255,255,0.3); } .code-keyword { color: #c678dd; } /* 紫色 */ .code-type { color: #e5c07b; } /* 黄色 */ .code-var { color: #e06c75; } /* 红色 */ .code-num { color: #d19a66; } /* 橙色 */ .code-comment { color: #5c6370; font-style: italic; } /* 灰色 */ /style /head body classbg-gray-100 min-h-screen flex flex-col items-center justify-center p-2 md:p-4 font-sans text-gray-800 div classmax-w-7xl w-full bg-white rounded-2xl shadow-2xl overflow-hidden flex flex-col !-- 头部标题 -- div classbg-gradient-to-r from-blue-600 to-indigo-700 text-white p-4 md:p-6 text-center h1 classtext-2xl md:text-3xl font-bold mb-2 滑动窗口 x 核心代码 同步演示/h1 p classtext-blue-200 text-sm md:text-base透视底层逻辑观察动画的同时看看 C 代码走到哪一行了/p /div !-- 动画主界面 (分左右两栏) -- div classp-4 md:p-6 flex-1 flex flex-col lg:flex-row gap-6 !-- 左侧动画演示区 -- div classflex-1 flex flex-col border-r-0 lg:border-r-2 border-gray-100 lg:pr-6 !-- 讲解信息框 -- div classbg-blue-50 border-l-4 border-blue-500 p-4 rounded-r-xl mb-6 min-h-[90px] flex items-center shadow-sm p idmessage-box classtext-base md:text-lg font-medium text-blue-900 leading-relaxed 准备开始用长度为 3 的“滑动窗口”扫描字符串并实时比对频率表。 /p /div !-- 数据面板频率表 结果 -- div classflex flex-col sm:flex-row gap-4 mb-8 items-stretch justify-center div classbg-gray-50 p-3 rounded-xl border-2 border-gray-100 shadow-inner flex-1 max-w-sm mx-auto w-full h3 classtext-center font-bold text-gray-500 mb-2 text-xs tracking-widest uppercase 字母频率表/h3 div classgrid grid-cols-6 gap-1 text-center div classfont-bold text-gray-400 text-xs py-1 border-b字母/div div classfont-bold text-gray-400 text-xs py-1 border-ba/div div classfont-bold text-gray-400 text-xs py-1 border-bb/div div classfont-bold text-gray-400 text-xs py-1 border-bc/div div classfont-bold text-gray-400 text-xs py-1 border-bd/div div classfont-bold text-gray-400 text-xs py-1 border-be/div div classfont-bold text-blue-600 text-xs py-1.5 bg-blue-50 rounded-lpCount/div div classfont-mono text-gray-700 py-1.5 bg-blue-501/div div classfont-mono text-gray-700 py-1.5 bg-blue-501/div div classfont-mono text-gray-700 py-1.5 bg-blue-501/div div classfont-mono text-gray-400 py-1.5 bg-blue-500/div div classfont-mono text-gray-400 py-1.5 bg-blue-50 rounded-r0/div div classfont-bold text-indigo-600 text-xs py-1.5 bg-indigo-50 rounded-l mt-1sCount/div div idcount-a classfont-mono text-gray-700 py-1.5 bg-indigo-50 mt-1 cell-transition0/div div idcount-b classfont-mono text-gray-700 py-1.5 bg-indigo-50 mt-1 cell-transition0/div div idcount-c classfont-mono text-gray-700 py-1.5 bg-indigo-50 mt-1 cell-transition0/div div idcount-d classfont-mono text-gray-400 py-1.5 bg-indigo-50 mt-1 cell-transition0/div div idcount-e classfont-mono text-gray-400 py-1.5 bg-indigo-50 mt-1 cell-transition rounded-r0/div /div /div div classbg-white p-3 rounded-xl shadow border border-green-200 flex flex-col items-center justify-center min-w-[120px] div classtext-xs text-green-600 font-bold mb-1✅ 结果起始下标/div div idresults-box classtext-2xl font-black text-green-500[]/div /div /div !-- 字符串 S 展示区 -- div classmb-8 relative h3 classtext-xs font-bold text-gray-400 mb-2 ml-2主字符串 s/h3 div classflex flex-nowrap justify-start md:justify-center gap-1 md:gap-2 overflow-x-auto pb-2 px-1 idstring-container !-- 方块动态生成 -- /div /div !-- 控制按钮区 -- div classflex justify-center gap-3 mt-auto flex-wrap button idbtn-reset classpx-5 py-2 bg-gray-200 hover:bg-gray-300 text-gray-700 font-semibold rounded-full shadow transition-colors text-sm 重置 /button button idbtn-step classpx-6 py-2 bg-blue-500 hover:bg-blue-600 text-white font-bold rounded-full shadow transition-transform transform hover:scale-105 text-sm 下一步 /button button idbtn-play classpx-6 py-2 bg-emerald-500 hover:bg-emerald-600 text-white font-bold rounded-full shadow transition-transform transform hover:scale-105 text-sm ▶️ 自动播放 /button /div /div !-- 右侧代码同步高亮区 -- div classw-full lg:w-5/12 bg-[#282c34] rounded-xl shadow-inner overflow-hidden flex flex-col div classbg-[#21252b] px-4 py-2 flex items-center border-b border-gray-700 div classflex gap-1.5 mr-4 div classw-3 h-3 rounded-full bg-red-500/div div classw-3 h-3 rounded-full bg-yellow-500/div div classw-3 h-3 rounded-full bg-green-500/div /div span classtext-gray-400 text-xs font-monoSolution.cpp/span /div div classp-4 font-mono text-xs md:text-sm text-gray-300 overflow-y-auto leading-loose flex-1 div idline-1 classcode-line px-2 py-0.5 code-comment// 1. 初始化频率数组/div div idline-2 classcode-line px-2 py-0.5span classcode-typevector/spanlt;span classcode-typeint/spangt; pCount(26, 0), sCount(26, 0);/div div idline-3 classcode-line px-2 py-0.5 code-comment mt-2// 2. 建立初始窗口/div div idline-4 classcode-line px-2 py-0.5span classcode-keywordfor/span (span classcode-typeint/span i 0; i lt; pLen; i) {/div div idline-5 classcode-line px-2 py-0.5 pl-6pCount[p[i] - a];/div div idline-6 classcode-line px-2 py-0.5 pl-6sCount[s[i] - a];/div div idline-7 classcode-line px-2 py-0.5}/div div idline-8 classcode-line px-2 py-0.5 code-comment mt-2// 3. 核对第一个窗口/div div idline-9 classcode-line px-2 py-0.5span classcode-keywordif/span (sCount pCount) {/div div idline-10 classcode-line px-2 py-0.5 pl-6res.push_back(0);/div div idline-11 classcode-line px-2 py-0.5}/div div idline-12 classcode-line px-2 py-0.5 code-comment mt-2// 4. 窗口开始向右滑动/div div idline-13 classcode-line px-2 py-0.5span classcode-keywordfor/span (span classcode-typeint/span i pLen; i lt; sLen; i) {/div div idline-14 classcode-line px-2 py-0.5 pl-6sCount[s[i] - a]; span classcode-comment ml-2// 吃进新字符/span/div div idline-15 classcode-line px-2 py-0.5 pl-6sCount[s[i - pLen] - a]--; span classcode-comment ml-2// 吐出旧字符/span/div div idline-16 classcode-line px-2 py-0.5 pl-6 mt-1span classcode-keywordif/span (sCount pCount) {/div div idline-17 classcode-line px-2 py-0.5 pl-10 text-[#56b6c2]res.push_back(i - pLen 1);/div div idline-18 classcode-line px-2 py-0.5 pl-6}/div div idline-19 classcode-line px-2 py-0.5}/div /div /div /div /div script const s cbaebabacd; const p abc; const pLen p.length; const sLen s.length; let currentFrameIndex 0; let isPlaying false; let playInterval; let frames []; const targetCounts { a: 1, b: 1, c: 1, d: 0, e: 0 }; function checkMatch(counts) { for (let char of [a, b, c, d, e]) { if ((counts[char] || 0) ! targetCounts[char]) return false; } return true; } function generateFrames() { frames []; let currentCounts { a: 0, b: 0, c: 0, d: 0, e: 0 }; let results []; frames.push({ sCount: {...currentCounts}, window: [-1, -1], results: [...results], msg: 首先初始化频率数组 bpCount/b 和 bsCount/b大小都是 26初始为 0。, activeCode: [1, 2] // 对应 HTML 中的 line id }); // 1. 初始化第一个窗口 frames.push({ sCount: {...currentCounts}, window: [0, 0], actionIdx: 0, actionType: add, results: [...results], msg: 【初始窗口】将左边前 ${pLen} 个字符吃进窗口。吃进 ${s[0]}。, activeCode: [3, 4, 5, 6, 7] }); currentCounts[s[0]]; frames.push({ sCount: {...currentCounts}, window: [0, 1], actionIdx: 1, actionType: add, results: [...results], msg: 【初始窗口】吃进 ${s[1]}。, activeCode: [3, 4, 5, 6, 7] }); currentCounts[s[1]]; frames.push({ sCount: {...currentCounts}, window: [0, 2], actionIdx: 2, actionType: add, results: [...results], msg: 【初始窗口】吃进 ${s[2]}。初始窗口建立完毕准备核对。, activeCode: [3, 4, 5, 6, 7] }); currentCounts[s[2]]; let isMatch checkMatch(currentCounts); if (isMatch) results.push(0); frames.push({ sCount: {...currentCounts}, window: [0, 2], match: isMatch, results: [...results], msg: 检查 sCount 和 pCount 是否相等。${isMatch ? 匹配成功记录下标 0。 : 不匹配。}, activeCode: isMatch ? [8, 9, 10, 11] : [8, 9, 11] }); // 2. 窗口滑动 for (let i pLen; i sLen; i) { let leftOut i - pLen; frames.push({ sCount: {...currentCounts}, window: [leftOut, i], actionIdx: i, actionType: add, results: [...results], msg: 【滑动】指针向右新吃进 b${s[i]}/b。频率 1。, activeCode: [12, 13, 14] }); currentCounts[s[i]]; frames.push({ sCount: {...currentCounts}, window: [leftOut 1, i], actionIdx: leftOut, actionType: remove, results: [...results], msg: 【滑动】为了保持长度为 ${pLen}必须吐出最左侧旧字符 b${s[leftOut]}/b。频率 -1。, activeCode: [15] }); currentCounts[s[leftOut]]--; isMatch checkMatch(currentCounts); if (isMatch) results.push(leftOut 1); frames.push({ sCount: {...currentCounts}, window: [leftOut 1, i], match: isMatch, results: [...results], msg: 比对更新后的窗口。${isMatch ? 匹配成功记录起始下标 b${leftOut 1}/b。 : 不匹配。}, activeCode: isMatch ? [16, 17, 18] : [16, 18] }); } frames.push({ sCount: {...currentCounts}, window: [-1, -1], results: [...results], end: true, msg: 循环结束返回结果。核心操作全在循环内的常数级加减完美 O(N), activeCode: [] }); } function render() { const frame frames[currentFrameIndex]; // 1. UI 文本 document.getElementById(message-box).innerHTML frame.msg; document.getElementById(results-box).innerHTML [ frame.results.join(, ) ]; // 2. 代码高亮同步 for (let i 1; i 19; i) { const lineEl document.getElementById(line-${i}); if (!lineEl) continue; if (frame.activeCode frame.activeCode.includes(i)) { lineEl.classList.add(code-highlight); } else { lineEl.classList.remove(code-highlight); } } // 3. 频率表 for (let char of [a, b, c, d, e]) { const el document.getElementById(count-${char}); const currentVal frame.sCount[char] || 0; el.innerText currentVal; el.classList.remove(freq-match, freq-mismatch, text-gray-400); if (frame.match ! undefined) { if (currentVal targetCounts[char]) el.classList.add(freq-match); else el.classList.add(freq-mismatch); } else { if (currentVal 0 targetCounts[char] 0) el.classList.add(text-gray-400); else el.classList.add(text-gray-800); } } // 4. 字符串 const container document.getElementById(string-container); container.innerHTML ; const [winStart, winEnd] frame.window; for (let i 0; i sLen; i) { const wrapper document.createElement(div); wrapper.className flex flex-col items-center flex-shrink-0; const idxLabel document.createElement(div); idxLabel.className text-[10px] md:text-xs font-bold text-gray-400 mb-1; idxLabel.innerText i; const box document.createElement(div); let boxClasses w-9 h-9 md:w-12 md:h-12 flex items-center justify-center text-lg md:text-xl font-bold border-[3px] rounded-lg cell-transition ; if (frame.end) boxClasses char-box opacity-50; else if (frame.match i winStart i winEnd) boxClasses char-match; else if (i frame.actionIdx) { if (frame.actionType add) boxClasses char-add; if (frame.actionType remove) boxClasses char-remove; } else if (i winStart i winEnd) boxClasses char-in-window; else boxClasses char-box; box.className boxClasses; box.innerText s[i]; wrapper.appendChild(idxLabel); wrapper.appendChild(box); container.appendChild(wrapper); } const isEnd currentFrameIndex frames.length - 1; document.getElementById(btn-step).disabled isEnd; document.getElementById(btn-step).className isEnd ? px-6 py-2 bg-gray-300 text-gray-500 font-bold rounded-full cursor-not-allowed shadow text-sm : px-6 py-2 bg-blue-500 hover:bg-blue-600 text-white font-bold rounded-full shadow transition-transform transform hover:scale-105 text-sm; } // --- 控制逻辑 --- document.getElementById(btn-step).addEventListener(click, () { if (currentFrameIndex frames.length - 1) { currentFrameIndex; render(); } }); document.getElementById(btn-reset).addEventListener(click, () { currentFrameIndex 0; if(isPlaying) togglePlay(); render(); }); document.getElementById(btn-play).addEventListener(click, togglePlay); function togglePlay() { const playBtn document.getElementById(btn-play); if (isPlaying) { clearInterval(playInterval); playBtn.innerHTML ▶️ 自动播放; playBtn.classList.replace(bg-orange-500, bg-emerald-500); playBtn.classList.replace(hover:bg-orange-600, hover:bg-emerald-600); isPlaying false; } else { if (currentFrameIndex frames.length - 1) currentFrameIndex 0; playBtn.innerHTML ⏸️ 暂停播放; playBtn.classList.replace(bg-emerald-500, bg-orange-500); playBtn.classList.replace(hover:bg-emerald-600, hover:bg-orange-600); isPlaying true; playInterval setInterval(() { if (currentFrameIndex frames.length - 1) { currentFrameIndex; render(); } else { togglePlay(); } }, 1500); // 稍微放慢到1.5秒一帧方便看清代码 } } generateFrames(); render(); /script /body /html