题目

1.自己想的垃圾方法

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        char[] sArray = s.toCharArray();
        char[] pArray = p.toCharArray();
        Arrays.sort(pArray);
        String pSorted = String.valueOf(pArray);
        Set<Character> pSet = new HashSet<>();
        for (char c : pArray) {
            pSet.add(c);
        }

        for (int i = 0; i <= s.length() - p.length(); ++i) {
            if (!pSet.contains(sArray[i])) {
                continue;
            }
            
            char[] tmpArray = new char[p.length()];
            for (int j = i; j - i < p.length(); ++j) {
                tmpArray[j - i] = sArray[j];
            }
            Arrays.sort(tmpArray);
            String tmp = String.valueOf(tmpArray);
            if (tmp.equals(pSorted)) {
                res.add(i);
            }
        }

        return res;
    }
}

2.滑动窗口

重点学习《算法小抄》上关于滑动窗口模板几道题的总结对比！

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        char[] sArray = s.toCharArray();
        char[] pArray = p.toCharArray();
        int[] need = new int[256];
        Set<Character> set = new HashSet<>();
        int[] window = new int[256];
        for (char c : pArray) {
            ++need[c];
            set.add(c);
        }
        int valid = 0,left = 0, right = 0;
        while (right < sArray.length) {
            char cur = sArray[right];
            ++right;
            if (need[cur] > 0) {
                ++window[cur];
                if (need[cur] == window[cur]) {
                    ++valid;
                }
            }
            while (right - left >= pArray.length) {
                if (valid == set.size()) {
                    res.add(left);
                }
                char d = sArray[left];
                ++left;
                if (need[d] > 0) {
                    if (window[d] == need[d]) {
                        --valid;
                    }
                    --window[d];
                }
            }
        }

        return res;
    }
}