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;}

 希望大家积极讨论！