LeetCode 热题100：找到字符串中所有字母异位词（Java 实现详解）

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^4
• s和p仅包含小写字母

🔍 原题分析

本题本质是：在主串s中找出所有长度等于p且字符频次完全相同的子串。

关键观察：

1. 异位词必须满足：长度相等 + 字符种类及频次完全一致。
2. 因此，我们只需在s中滑动一个固定长度为p.length()的窗口，检查每个窗口是否与p构成异位词。
3. 直接对每个子串排序再比较？时间复杂度过高（O(n·m log m)），不可取。
4. 更优策略：使用字符频次统计 + 滑动窗口。

💡 答案构思

核心思想：滑动窗口 + 字符频次数组

1. 若s.length() < p.length()，直接返回空列表。
2. 使用两个长度为26的整型数组（因只有小写字母）分别记录：
   • pCount：字符串p中各字符出现次数；
   • sCount：当前滑动窗口中各字符出现次数。
3. 初始化第一个窗口（s[0..pLen-1]）的sCount。
4. 若sCount == pCount，则索引0是答案。
5. 滑动窗口：每次移除左边界字符，加入右边界新字符，更新sCount，并判断是否匹配。

此方法避免了重复遍历整个窗口，仅需 O(1) 更新频次。

✅ 完整答案（Java）

importjava.util.*;publicclassSolution{publicList<Integer>findAnagrams(Strings,Stringp){intsLen=s.length(),pLen=p.length();if(sLen<pLen){returnnewArrayList<>();}List<Integer>ans=newArrayList<>();int[]sCount=newint[26];int[]pCount=newint[26];// 初始化 p 的字符频次 和 s 的第一个窗口for(inti=0;i<pLen;i++){sCount[s.charAt(i)-'a']++;pCount[p.charAt(i)-'a']++;}// 检查第一个窗口if(Arrays.equals(sCount,pCount)){ans.add(0);}// 滑动窗口：从 i=0 到 i = sLen - pLen - 1for(inti=0;i<sLen-pLen;i++){// 移除左边字符sCount[s.charAt(i)-'a']--;// 添加右边新字符sCount[s.charAt(i+pLen)-'a']++;// 检查当前窗口if(Arrays.equals(sCount,pCount)){ans.add(i+1);}}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时，说明完全匹配！

优化后代码（Java）

publicList<Integer>findAnagrams(Strings,Stringp){intsLen=s.length(),pLen=p.length();if(sLen<pLen)returnnewArrayList<>();List<Integer>ans=newArrayList<>();int[]count=newint[26];// 初始化差值数组：窗口 - pfor(inti=0;i<pLen;i++){count[s.charAt(i)-'a']++;count[p.charAt(i)-'a']--;}// 计算初始 differintdiffer=0;for(intc:count){if(c!=0)differ++;}if(differ==0)ans.add(0);for(inti=0;i<sLen-pLen;i++){charleftChar=s.charAt(i);charrightChar=s.charAt(i+pLen);// 移除 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(differ==0)ans.add(i+1);}returnans;}

优化后复杂度

• 时间复杂度：O(n + m + Σ) = O(n)（每次窗口移动仅 O(1) 判断）
• 空间复杂度：O(1)

虽然常数级优化，但在大数据量下性能更优。

❓ 问题解答（FAQ）

Q1：为什么不用 HashMap 而用数组？
A：因为题目限定“仅小写字母”，数组索引直接对应字符，比 HashMap 更快、更省空间。

Q2：能否处理 Unicode 字符？
A：若支持任意字符，需改用HashMap<Character, Integer>，但本题无需。

Q3：窗口大小固定吗？
A：是的！因为异位词必须与p长度相同，所以窗口大小恒为p.length()。

📚 数据结构与算法基础知识点回顾

💬 面试官提问环节（模拟）

Q：如果字符串包含大写字母和数字，你的解法需要怎么改？
A：可改用HashMap<Character, Integer>存储频次，或扩大数组至 128（覆盖 ASCII）。

Q：能否用双指针？和滑动窗口有什么区别？
A：本题窗口大小固定，严格来说是“定长滑动窗口”。双指针通常用于变长窗口（如最小覆盖子串）。

Q：如果要求返回所有异位词子串本身，而不仅是索引？
A：可在匹配时ans.add(s.substring(i, i + pLen))，但注意 substring 在 Java 中是 O(k) 操作。

🛠️ 实际开发中的应用场景

1. 敏感词检测：检测用户输入是否包含某关键词的变体（如乱序拼写绕过）。
2. 日志分析：在日志流中查找特定模式的排列组合。
3. 生物信息学：DNA 序列中查找特定碱基组合的异构体。
4. 文本相似度：初步判断两段文本是否由相同词汇构成（忽略顺序）。

🔗 相关题目推荐

📝 总结与延伸

本题是滑动窗口 + 字符频次统计的经典范例。通过固定窗口大小，我们高效地在 O(n) 时间内解决了异位词查找问题。

关键收获：

• 滑动窗口适用于“固定长度子串”问题；
• 字符频次数组是处理字母类问题的利器；
• 通过differ优化可将比较操作降至 O(1)；
• 实际工程中，此类算法可用于文本模式识别、安全过滤等场景。

延伸思考：如果p很长（如 10^5），而s更长（10^6），是否还有优化空间？可以考虑Rabin-Karp 滚动哈希，但需处理哈希冲突。

✅掌握本题，你就掌握了滑动窗口在字符串匹配中的核心思想！

👉 如果你觉得本文对你有帮助，欢迎点赞、收藏、评论！也欢迎关注我的 CSDN 主页，获取更多高质量算法解析。