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

本来计划用排序的方式，超时了

class Solution {
    /**
    2024.6.16
    遍历数据，每次取子串排序，和目标串p对比下，但超时了，虽然超时了，但权当熟悉java语法了
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res=new ArrayList<>();
        char[] targetChars=p.toCharArray();
        Arrays.sort(targetChars);
        String targetStr=new String(targetChars);
        int len=p.length();
        for(int i=0;i<=s.length()-len;i++){
            String tmp=s.substring(i,i+len);
            char[] chars=tmp.toCharArray();
            Arrays.sort(chars);
            String tmpStr=new String(chars);
            if(targetStr.equals(tmpStr)){
                res.add(i);
            }
        }
        return res;
    }
}

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

换种思路，其实比较abc和bac是异位词，不需要完全排序，只要它们对应字符一样就可以判定是一样的，比如a都出现1次，b都出现1次，c都出现1次。用这种思路判断，不用排序。

class Solution {
    /**
    2024.6.16
    思路：其实比较abc和bac这2个异位词，不需要完全排序，只要它们对应字符一样就可以判定是一样的，
    比如a都出现1次，b都出现1次，c都出现1次。用这种思路判断，不用排序。所以先对目标串p统计出一个
    计数数组pChars，然后给源串s也搞一个sChars，但是滑动的搞一个，这样遍历的时候，i从0开始，当i变成1
    了，sChars减一下，加一下就可以了，这样效率很高。

     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res=new ArrayList<>();
        int sLen=s.length(),pLen=p.length();

        if(pLen>sLen){
            return res;
        }
        char[] sChars=new char[26];
        char[] pChars=new char[26];
        for(int i=0;i<pLen;i++){
            sChars[s.charAt(i)-'a']++;
            pChars[p.charAt(i)-'a']++;
        }
        for(int i=0;i<sLen-pLen;i++){
            if(match(sChars,pChars)){
                res.add(i);
            } 
            // 移动下标，这个时候需要更新s字符串对应的字符统计数组
            // 最后一次循环的时候，i=sLen-pLen-1，那i+pLen就等于sLen-1
            sChars[s.charAt(i)-'a']--;
            sChars[s.charAt(i+pLen)-'a']++;
        }
        // 给最后一组匹配判断下 sLen-pLen到sLen-1
        if (match(sChars, pChars)) {
            res.add(sLen - pLen);
        }

        return res;
    }

    public boolean match(char[] sChars, char[] pChars){
        for(int i=0;i<26;i++){
            if(sChars[i]!=pChars[i]){
                return false;
            }
        }
        return true;
    }
}