企业官网建设流程全解析

宝塔面板做网站不能打开PHP显示404,wordpress输出文章标签名,移植wordpress数据库,百度论坛发帖LeetCode 热题100#xff1a;找到字符串中所有字母异位词#xff08;Java 实现详解#xff09;本文将深入剖析 LeetCode 第438题《找到字符串中所有字母异位词》#xff0c;从题目理解、解题思路到代码实现、复杂度分析#xff0c;再到面试高频问题与实际应用场景#xf…LeetCode 热题100找到字符串中所有字母异位词Java 实现详解本文将深入剖析 LeetCode 第438题《找到字符串中所有字母异位词》从题目理解、解题思路到代码实现、复杂度分析再到面试高频问题与实际应用场景助你彻底掌握滑动窗口算法在字符串匹配中的应用。 原题回顾题目描述给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。异位词Anagram指由相同字母重排列组成的字符串包括原字符串本身例如abc与bca是异位词。示例输入: s cbaebabacd, p abc 输出: [0,6] 解释: - 起始索引 0: cba → abc 的异位词 - 起始索引 6: bac → abc 的异位词 输入: s abab, p ab 输出: [0,1,2]约束条件1 s.length, p.length 3 * 10^4s和p仅包含小写字母 原题分析本题本质是在主串s中找出所有长度等于p且字符频次完全相同的子串。关键观察异位词必须满足长度相等 字符种类及频次完全一致。因此我们只需在s中滑动一个固定长度为p.length()的窗口检查每个窗口是否与p构成异位词。直接对每个子串排序再比较时间复杂度过高O(n·m log m)不可取。更优策略使用字符频次统计 滑动窗口。 答案构思核心思想滑动窗口 字符频次数组若s.length() p.length()直接返回空列表。使用两个长度为26的整型数组因只有小写字母分别记录pCount字符串p中各字符出现次数sCount当前滑动窗口中各字符出现次数。初始化第一个窗口s[0..pLen-1]的sCount。若sCount pCount则索引0是答案。滑动窗口每次移除左边界字符加入右边界新字符更新sCount并判断是否匹配。此方法避免了重复遍历整个窗口仅需 O(1) 更新频次。✅ 完整答案Javaimportjava.util.*;publicclassSolution{publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length(),pLenp.length();if(sLenpLen){returnnewArrayList();}ListIntegeransnewArrayList();int[]sCountnewint[26];int[]pCountnewint[26];// 初始化 p 的字符频次 和 s 的第一个窗口for(inti0;ipLen;i){sCount[s.charAt(i)-a];pCount[p.charAt(i)-a];}// 检查第一个窗口if(Arrays.equals(sCount,pCount)){ans.add(0);}// 滑动窗口从 i0 到 i sLen - pLen - 1for(inti0;isLen-pLen;i){// 移除左边字符sCount[s.charAt(i)-a]--;// 添加右边新字符sCount[s.charAt(ipLen)-a];// 检查当前窗口if(Arrays.equals(sCount,pCount)){ans.add(i1);}}returnans;}} 代码分析字符映射利用a ~ z的 ASCII 连续性通过ch - a映射到 0~25。窗口滑动左边界i移出 →sCount[s[i] - a]--右边界i pLen移入 →sCount[s[i pLen] - a]比较方式使用Arrays.equals()直接比较两个 int 数组是否相等简洁高效。⏱️ 时间复杂度 空间复杂度分析方法一基础滑动窗口时间复杂度O(m (n - m) × Σ)m p.length(),n s.length(),Σ 26小写字母数初始化pCount和第一个窗口O(m)共n - m 1个窗口每次比较数组需 O(Σ)总体 ≈O(n × 26) O(n)常数可忽略空间复杂度O(Σ) O(26) O(1)仅使用两个固定长度的数组 优化思路差值计数 differ 变量上述方法每次都要比较整个数组26次操作。可进一步优化核心思想维护一个count[26]数组表示窗口字符频次 - p字符频次的差值。引入differ记录有多少个字母的差值 ≠ 0。当differ 0时说明完全匹配优化后代码JavapublicListIntegerfindAnagrams(Strings,Stringp){intsLens.length(),pLenp.length();if(sLenpLen)returnnewArrayList();ListIntegeransnewArrayList();int[]countnewint[26];// 初始化差值数组窗口 - pfor(inti0;ipLen;i){count[s.charAt(i)-a];count[p.charAt(i)-a]--;}// 计算初始 differintdiffer0;for(intc:count){if(c!0)differ;}if(differ0)ans.add(0);for(inti0;isLen-pLen;i){charleftChars.charAt(i);charrightChars.charAt(ipLen);// 移除 leftCharif(count[leftChar-a]1)differ--;// 从 1→0差异消失elseif(count[leftChar-a]0)differ;// 从 0→-1新增差异count[leftChar-a]--;// 添加 rightCharif(count[rightChar-a]-1)differ--;// 从 -1→0elseif(count[rightChar-a]0)differ;// 从 0→1count[rightChar-a];if(differ0)ans.add(i1);}returnans;}优化后复杂度时间复杂度O(n m Σ) O(n)每次窗口移动仅 O(1) 判断空间复杂度O(1)虽然常数级优化但在大数据量下性能更优。❓ 问题解答FAQQ1为什么不用 HashMap 而用数组A因为题目限定“仅小写字母”数组索引直接对应字符比 HashMap 更快、更省空间。Q2能否处理 Unicode 字符A若支持任意字符需改用HashMapCharacter, Integer但本题无需。Q3窗口大小固定吗A是的因为异位词必须与p长度相同所以窗口大小恒为p.length()。 数据结构与算法基础知识点回顾知识点说明滑动窗口用于解决子数组/子串问题维护一个动态窗口避免重复计算字符频次统计使用数组或哈希表记录字符出现次数常用于异位词、排列等问题ASCII 映射a的 ASCII 是 97ch - a可将小写字母映射到 0~25数组比较Arrays.equals(arr1, arr2)可逐元素比较两个数组 面试官提问环节模拟Q如果字符串包含大写字母和数字你的解法需要怎么改A可改用HashMapCharacter, Integer存储频次或扩大数组至 128覆盖 ASCII。Q能否用双指针和滑动窗口有什么区别A本题窗口大小固定严格来说是“定长滑动窗口”。双指针通常用于变长窗口如最小覆盖子串。Q如果要求返回所有异位词子串本身而不仅是索引A可在匹配时ans.add(s.substring(i, i pLen))但注意 substring 在 Java 中是 O(k) 操作。️ 实际开发中的应用场景敏感词检测检测用户输入是否包含某关键词的变体如乱序拼写绕过。日志分析在日志流中查找特定模式的排列组合。生物信息学DNA 序列中查找特定碱基组合的异构体。文本相似度初步判断两段文本是否由相同词汇构成忽略顺序。 相关题目推荐题号题目关联点LeetCode 567字符串的排列几乎相同只需返回是否存在LeetCode 76最小覆盖子串变长滑动窗口 频次匹配LeetCode 438本题—LeetCode 242有效的字母异位词判断两个字符串是否为异位词LeetCode 1004最大连续1的个数 III滑动窗口思想 总结与延伸本题是滑动窗口 字符频次统计的经典范例。通过固定窗口大小我们高效地在 O(n) 时间内解决了异位词查找问题。关键收获滑动窗口适用于“固定长度子串”问题字符频次数组是处理字母类问题的利器通过differ优化可将比较操作降至 O(1)实际工程中此类算法可用于文本模式识别、安全过滤等场景。延伸思考如果p很长如 10^5而s更长10^6是否还有优化空间可以考虑Rabin-Karp 滚动哈希但需处理哈希冲突。✅掌握本题你就掌握了滑动窗口在字符串匹配中的核心思想 如果你觉得本文对你有帮助欢迎点赞、收藏、评论也欢迎关注我的 CSDN 主页获取更多高质量算法解析。