当前位置：首页 > news >正文

力扣解题-438. 找到字符串中所有字母异位词

news 2026/5/12 11:04:15

力扣解题-438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:

输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

第一次解答

解题思路

核心方法：滑动窗口 + 排序对比，通过固定长度的滑动窗口遍历s的所有子串，将子串和p分别排序后对比是否相等，以此判断是否为异位词，逻辑直观但时间效率极低。

具体步骤：

初始化结果列表result，用于存储符合条件的子串起始索引。
定义滑动窗口的左右边界：left初始为0，right初始为p的长度（窗口长度固定为p的长度，因为异位词长度必与p相同）。
预处理p字符串：将p转为字符数组并排序（Arrays.sort(pArray)），得到p的“标准有序形式”（异位词排序后结果相同）。
滑动窗口遍历s字符串（终止条件：right <= s.length()）：
a. 截取当前窗口内的子串s1 = s.substring(left, right)；
b. 将s1转为字符数组并排序（Arrays.sort(s1Array)）；
c. 对比排序后的s1数组和p数组是否相等：若相等，说明当前子串是p的异位词，将left加入结果列表；
d. 窗口右移：left++、right++，继续检查下一个窗口。
遍历完成后，返回结果列表result。

失败/性能劣势原因分析

该解法耗时1688ms仅击败5.37%用户，核心问题是时间复杂度过高，无法适配题目数据规模：

时间复杂度为O(n×m×logm)（n为s的长度，m为p的长度）：
- 滑动窗口遍历s需执行n - m + 1次（约O(n)）；
- 每次遍历需对窗口子串（长度m）和p（长度m）分别排序，排序的时间复杂度为O(m×logm)；
- 总计算量约为O(n×m×logm)，对于n=3×10⁴、m=3×10⁴的极端情况，计算量会达到3×10⁴ × 3×10⁴ × 15 ≈ 1.35×10⁹，远超时间阈值，导致耗时极长。
冗余操作：每次窗口滑动都要重新截取子串、转数组、排序，存在大量重复计算（如相邻窗口仅首尾字符不同，却要对整个子串重新排序）。
内存表现差：频繁的字符串截取、数组转换操作会产生大量临时对象，导致内存消耗偏高（46.73MB仅击败16.10%用户）。

publicList<Integer>findAnagrams(Strings,Stringp){List<Integer>result=newArrayList();intleft=0;intright=p.length();char[]pArray=p.toCharArray();Arrays.sort(pArray);while(right<=s.length()){Strings1=s.substring(left,right);char[]s1Array=s1.toCharArray();Arrays.sort(s1Array);if(Arrays.equals(pArray,s1Array)){result.add(left);}left++;right++;}returnresult;}

第二次解答

解题思路

核心方法：滑动窗口 + 字符计数对比，利用“异位词的字符出现次数完全相同”的特性，通过数组统计字符频次，替代排序对比，将时间复杂度优化至O(n)，大幅提升性能。

具体步骤：

核心原理铺垫：异位词的本质是“每个字符的出现次数完全一致”，因此无需排序，只需统计26个小写字母的出现次数，对比频次数组即可判断是否为异位词。
初始化两个长度为26的数组（对应26个小写字母）：
- pCount：统计p中每个字符的出现次数；
- sCount：统计s中当前滑动窗口内每个字符的出现次数。
预处理p的字符频次：遍历p的每个字符，通过p.charAt(i)-'a'将字符映射为0-25的数组索引，对应位置计数加1（如字符’a’对应索引0，'b’对应索引1）。
滑动窗口统计s的字符频次：遍历s的每个字符（索引i）：
a. 将当前字符的频次计入sCount（sCount[s.charAt(i)-'a']++）；
b. 若i >= p.length()（窗口长度超过p的长度），需移除窗口左侧的字符频次：sCount[s.charAt(i-p.length())-'a']--（保证sCount仅统计当前窗口内的字符）；
c. 对比pCount和sCount是否相等：若相等，说明当前窗口内的子串是p的异位词，计算子串起始索引（i - p.length() + 1）并加入结果列表。
遍历完成后，返回结果列表result。

核心优化逻辑说明

时间复杂度优化：
- 预处理p的频次：O(m)（m为p的长度）；
- 遍历s统计频次：O(n)（n为s的长度），每个字符仅执行“计数+1/计数-1”的O(1)操作；
- 对比频次数组：Arrays.equals对比26个元素，属于O(1)操作；
- 总时间复杂度为O(n + m)，接近O(n)，相比第一次解答的O(n×m×logm)，性能提升数个量级，耗时从1688ms降至11ms。
空间优化：仅使用两个长度为26的固定数组（总占用52个int空间），无频繁的字符串/数组临时对象创建，内存消耗降至46.1MB，击败52.64%用户。
滑动窗口的高效性：窗口移动时仅更新首尾字符的频次，无需重新处理整个窗口，消除了第一次解答的重复排序开销。

执行耗时:11 ms,击败了42.26% 的Java用户
内存消耗:46.1 MB,击败了52.64% 的Java用户

publicList<Integer>findAnagrams(Strings,Stringp){List<Integer>result=newArrayList();int[]pCount=newint[26];int[]sCount=newint[26];//因为ASCII 码差值计算，小写字母 'a' 到 'z' 在 ASCII 表中是连续编码的：//'a' → ASCII 值 97，'b' → 98，'c' → 99，直到'z' → 122//字符 - 'a' 的结果：'a' - 'a' = 0，'b' - 'a' = 1，'c' - 'a' = 2，直到'z' - 'a' = 25//这样就将 26 个字母映射到 0~25 的整数，完美对应数组索引。for(inti=0;i<p.length();i++){pCount[p.charAt(i)-'a']++;}for(inti=0;i<s.length();i++){sCount[s.charAt(i)-'a']++;if(i>=p.length()){//移出第一个字符的数量sCount[s.charAt(i-p.length())-'a']--;}//判断是否相等if(Arrays.equals(pCount,sCount)){result.add(i-p.length()+1);}}returnresult;}