009找到字符串中所有字母异位词

找到字符串中所有字母异位词题目链接https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListInteger findAnagrams(String s, String p) { int sLengths.length(), pLengthp.length(); int[] count new int[26]; for(int i0; ipLength; i){ count[p.charAt(i)-a]; } ListInteger ans new ArrayList(); int l0,rl; while(rsLength){ while(rsLengthrlpLengthcount[s.charAt(r)-a]!0){ count[s.charAt(r)-a]--; r; } if(rsLengthrlpLength){ if(!p.contains(String.valueOf(s.charAt(r)))){ while(lr){ count[s.charAt(l)-a]; l; } l; r; }else{ count[s.charAt(l)-a]; l; } continue; } if(rlpLength){ ans.add(l); count[s.charAt(l)-a]; l; } if(rsLength){ break; } } return ans; }分析代码的时间复杂度为O(n)空间复杂度为O(Σ)Σ 为所有可能的字符数。我的思路是利用count数组维护滑动窗口中字符串s的子串要与字符串p构成异位词还需要的字符及个数然后字符串s用双指针维护一个滑动窗口窗口的左指针指向异位词的开头右指针不断向右移动直到维护的窗口长度达到字符串p的长度或遇到不属于p的字符或遇到属于p但是个数以及满足了的字符然后分情况进行讨论在下方我只讨论两种情况其他情况较为简单暂不做讨论。​ 情况一遇到不属于p的字符。此时直接将左指针和右指针都移动到右指针的下一个位置直接开始下一轮循环。注意移动指针的同时还需要将count中l走过的位置中属于p的字符的个数减一。​ 情况二遇到属于p但是个数以及满足了的字符。此时只需将count中左指针指向的字符个数减一然后将左指针向后移动一位直接开启下一轮循环。看了官方题解后的解答//方法一滑动窗口 //时间复杂度O(m(n−m)×Σ) //空间复杂度O(Σ) //n 为字符串 s 的长度m 为字符串 p 的长度Σ 为所有可能的字符数。 public ListInteger findAnagrams(String s, String p) { int sLens.length(), pLenp.length(); if(sLenpLen){ return new ArrayListInteger(); } int[] sCount new int[26]; int[] pCount new int[26]; ListInteger ans new ArrayList(); for(int i0; ipLen; i){ sCount[s.charAt(i)-a]; pCount[p.charAt(i)-a]; } if(Arrays.equals(sCount,pCount)){ ans.add(0); } for(int i0; isLen-pLen; i){ sCount[s.charAt(i)-a]--; sCount[s.charAt(ipLen)-a]; if(Arrays.equals(sCount,pCount)){ ans.add(i1); } } return ans; } //方法二优化的滑动窗口 //时间复杂度O(nmΣ) //空间复杂度O(Σ) //n 为字符串 s 的长度m 为字符串 p 的长度Σ 为所有可能的字符数。 public ListInteger findAnagrams(String s, String p) { int sLens.length(), pLenp.length(); if(sLenpLen){ return new ArrayListInteger(); } int[] count new int[26];//维护当前窗口中的子串需要和p构成异位词缺少的字符个数 ListInteger ans new ArrayList(); for(int i0; ipLen; i){ count[s.charAt(i)-a]; count[p.charAt(i)-a]--; } int diff0;//维护当前窗口中子串的字符个数与p的字符个数不相同的个数 for(int i0; i26; i){ if(count[i]!0){ diff; } } if(diff0){ ans.add(0); } for(int i0; isLen-pLen; i){ if(count[s.charAt(i)-a]0){//从0——-1即这个字符的个数从相同变得不同 diff; } else if(count[s.charAt(i)-a]1){//从1——0即这个字符的个数从相同变得不同 diff--; } count[s.charAt(i)-a]--; if(count[s.charAt(ipLen)-a]-1){//从-1——0即这个字符的个数从不同变得相同 diff--; } else if(count[s.charAt(ipLen)-a]0){//从0——1即这个字符的个数从不同变得相同 diff; } count[s.charAt(ipLen)-a]; if(diff0){ ans.add(i1); } } return ans; }分析​ 1、方法一和方法二都采用滑动窗口解题用滑动窗口构造一个长度等于p的长度的s的子串。​ 2、方法一直接用两个数组各自维护窗口中s子串的字符个数和p的字符个数然后每次通过比较两个数组内容是否相同从而判断当前窗口构造的子串是否是p的异位词。​ 3、方法二只维护了一个diff即当前窗口构造的子串的字符个数与p的字符个数不同的总个数只需根据窗口每次的变化判断是否对diff产生影响最后通过判断diff是否等于0来判断当前窗口构造的子串是否是p的异位词。总结本题主要是用滑动窗口构造一个与p长度相等的s的子串然后采用“两个数组分别维护各自的字符数量从而进行比较”或“只维护两个字符串中个数不相等的字符的个数”来判断是否是异位词即可。