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

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

将题目意思转换后，即为在s中找到与p相同长度的字符串并且其中的字符要一一对应，但字符顺序可以改变；

1.常规解法

我们可以用一个数组将p的每种字符个数统计在数组中，遍历s，找到与p长度相同的子串，并将子串中的字符与p的字符进行比较，代码如下：

    public List<Integer> findAnagrams(String s, String p) {
        int pLen = p.length();
        int[] arrP = new int[128];
        int sLen = s.length();
        for (int i = 0; i < pLen; i++) {//将p的字符统计到arrP中
            char ch = p.charAt(i);
            arrP[ch]++;
        }
        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < sLen - pLen + 1; i++) {
            String sub = s.substring(i, i + pLen);//在s中找到与P长度相同的子串
            int[] arrSub = new int[128];
            for (int j =  0; j < pLen; j++) {//将子串的字符统计到数组中
                char ch = sub.charAt(j);
                arrSub[ch]++;
            }
            if (isSameArray(arrP, arrSub)) {
                ret.add(i);
            }
        }
        return ret;
    }

    private boolean isSameArray(int[] arr1, int[] arr2) {//比较两个数组是否相同
        int n1 = arr1.length;
        int n2 = arr2.length;
        for (int i = 0; i < n1; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

2.滑动窗口

在上述逻辑中，第一次与第二次判断会有重合部分，于是可以使用滑动窗口；

先定义两个指针left与right，两指针均指向s的第一个字符，再定义一个数组arrP用来存放p字符的种类与个数，用count来记录s子串中有效字符的个数，用数组arrSub存放子串中字符的种类与个数；

先让right向右移动，将right指向的字符存放到arrSub中，若该字符在arrSub中的值小于或等于在arrP中的值，就说明这个字符是一个有效字符，将count++；当right与left的距离等于p的长度时，就说明right与left之间的字符个数大于p的字符个数，若left指向的字符在arrSub中的值小于或等于arrP中的值，就说明这个字符是一个有效字符，需要将count--，并将left指向的字符从arrSub中移除一个，再将left右移一位，若count与pLen相等时，就说明right与left之间的字符与p的字符一一对应，就是一个异位词，将left存放到结果集中，接下来继续进行循环，流程图与代码如下：

    public List<Integer> findAnagrams(String s, String p) {
        int pLen = p.length();
        int sLen = s.length();
        int[] arrP = new int[128];
        for (int i = 0; i < pLen; i++) {
            char ch = p.charAt(i);
            arrP[ch]++;
        }
        List<Integer> ret = new ArrayList<>();//结果集
        int[] arrSub = new int[128];
        for (int left = 0, right = 0, count = 0; right < sLen; right++) {
            char in = s.charAt(right);
            arrSub[in]++;
            if (arrSub[in] <= arrP[in]) {//字符有效
                count++;
            }
            if (right - left >= pLen) {
                char out = s.charAt(left++);
                if (arrSub[out] <= arrP[out]) {//需要移除的是有效字符
                    count--;
                }
                arrSub[out]--;
            }
            if (count == pLen) {
                ret.add(left);
            }
        }
        return ret;
    }

 希望大家积极讨论！