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

 刷刷刷题找工作！

题目链接

. - 力扣（LeetCode）

自己的思路

只有暴力解法，从左至右遍历从s中截取长度与p相等的子字符串，放入HashSet中，再与p中字符一一对比，相同则可以。

知识点1

String(字符数组）转为List字符串类，list = Arrays.asList（string);

知识点2

获取字符串的index字符，s.charAt(index);

错误答案

写了好多，实在进行不下去了，放弃了

class Solution {public List<Integer> findAnagrams(String s, String p) {//划分p.len长度，然后比较是否包含其中所有字符串，扔一个，加一个，如果全部都有则有，负责继续向前增长int slen = s.length(), plen = p.length();List<Integer> ans = new ArrayList<Integer>();if(slen < plen){return ans;}int k = 0;//k表示上一个子字符串是否满足条件int i = 0, j = plen - 1;for(; i < slen - plen + 1; i ++, j++){if(k == 1){//上一次满足条件if(s.charAt(i - 1) == s.charAt(j)){k = 1;}}else{//注意不是以所有字符存在set中算成功，可能是同一个字符全在set中，应该是set中的数据全在截断字符中才对String ss = s.substring(i, j + 1);//截取字符Set<Character> set = new HashSet(Arrays.asList(ss));for(int l = 0 ; l < plen; l++){if(!set.contains(p.charAt(l))){k = 0;break;}k = 1;}}if(k == 1){ans.add(i);}}return ans;}
}

正确答案

这个题解非常妙的一点是，右节点是从0开始的，频率一点点加入scnt，且在这一个字符时，保证前面所有的字符要么与scnt相等要么小于。

相等意味着无需移动，小于意味着长度还不够，需要右边界继续向右移动。

而scnt>pcnt意味着加入的这个字符导致多了，需要在循环里移动直至相等。

class Solution {public List<Integer> findAnagrams(String s, String p) {int n = s.length(), m = p.length();List<Integer> ans = new ArrayList<Integer>();if(n < m){return ans;}int[] pcnt = new int[26];int[] scnt = new int[26];for(int i = 0; i < m ; i++){pcnt[p.charAt(i)-'a']++;}int left = 0;for(int right = 0; right < n ;right++){//这里是右边，从0开始慢慢加再到nint curRight = s.charAt(right) - 'a';//右边scnt[curRight]++;//由于动的只有scnt，且只会增加，所以后面的比较只可能是scnt>pcntwhile(scnt[curRight] > pcnt[curRight]){//比p中多，说明要移动左边int curleft = s.charAt(left) - 'a';scnt[curleft]--;left++;}//现在已经所有的字母都相同了，因为我相同了才会往后走，对每一次新加的最右端都进行了处理if(right - left + 1 == m){ans.add(left);}}return ans;}
}

太厉害了，学到了学到了