leetcode 438.找到字符串中所有字母异位词

思路：其实就是用滑动窗口的头脑，想象出来一个定长的窗口，在原字符串上进行移动，然后判断这个里面的字母是不是和所给字母全部一样。这个实现可以用循环然后用String的substring来模仿滑动窗口。
另有一个题目在于我们怎么判断窗口里面的字母和参照组的字符串里面的字母就是一样的呢？
有一个惯常的方法，就是把所给匹配的字符串排序，然后再把窗口中的字符进行排序，然后对比它们是不是相同的，如许就能判断了。
Java中的sort运用条件是需要转化字符串数组进行排序，需要留意。

1. class Solution {
2.     public List<Integer> findAnagrams(String s, String p) {
3.         int len=p.length();
4.         List<Integer>ans=new ArrayList<Integer>();
5.         char[]you=p.toCharArray();
6.         Arrays.sort(you);
7.         String tiaojian=new String(you);
8.         for(int i=0;i<s.length()-len+1;i++){
9.             String buf=s.substring(i,i+len);
10.             char[]arr=buf.toCharArray();
11.             Arrays.sort(arr);
12.             String res=new String(arr);
13.             if(res.equals(tiaojian)){
14.                 ans.add(i);
15.             }
16.         }
17.         return ans;
18.     }
19. }

复制代码

思路二：也是滑动窗口的思路，但是不一样的是，我们这里的判断条件不一样了，定义两个数组进行比较，这两个数组一个表现s字符串中滑动窗口的字母频次，另一个则表现p字符串的字母频次。
我们这里用了双指针代表滑动窗口的模仿，当窗口长度为p字符串的长度的时候，我们就进行比较它们两个的频次数组是不是完全一样。假如一样，就分析是，把左指针指向的下标装入效果数组中；不是，就同时移动左指针和右指针一个单位，再次进行比较。

1. class Solution {
2.     public List<Integer> findAnagrams(String s, String p) {
3.         int len1=s.length();
4.         int len2=p.length();
5.         List<Integer>ans=new ArrayList<Integer>();
6.         int[]a1=new int[26];
7.         int[]a2=new int[26];
8.         int l=0,r=0;
9.         for(int i=0;i<len2;i++)a2[p.charAt(i)-'a']++;
10.         while(r<len1){
11.             a1[s.charAt(r)-'a']++;
12.             if(r-l+1>len2)a1[s.charAt(l++)-'a']--;
13.             if(check(a1,a2))ans.add(l);
14.             r++;
15.         }
16.         return ans;
17.     }
18.     public boolean check(int[]s1,int[]s2){
19.         for(int i=0;i<26;i++){
20.             if(s1[i]!=s2[i])
21.             return false;
22.         }
23.         return true;
24.     }
25. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。