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

滑动窗口

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List findAnagrams(String s, String p) {

        /**
         * 滑动窗口
         * 始终设置一个长度等于p的区间来判断。将p中字符出现的次数保存在对应的ASCII码数组中
         */
        int left = 0;
        int right = p.length() - 1;
        int[] count = new int[26];
        List list = new ArrayList();

        for (int i = 0; i < p.length(); i++) {
            count[p.charAt(i) - 'a']++;
        }

        while (left < s.length() - p.length() + 1){

            int[] copy = Arrays.copyOf(count, count.length);

            for (int i = left; i <= right; i++) {

                /**
                 * 只要该区间有一个元素重复出现或者根本不在p中，就结束循环
                 * 满足条件则该字符的次数减1
                 */
                if (copy[s.charAt(i) - 'a'] == 0){
                    break;
                }
                else {
                    copy[s.charAt(i) - 'a']--;
                }
            }

            /**
             * 因为不满足条件时会直接终止for循环，所以要判断一下
             * 如果copy数组的和为0，说明当前区间包含的字符和p一样
             */
            if (Arrays.stream(copy).sum() == 0){
                list.add(left);
            }

            left++;
            right++;
        }

        return list;
    }
}

/**
 * 时间复杂度 O(p^2)
 * 空间复杂度 O(s-p)
 */

优化1——减少重复的次数记录

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List findAnagrams(String s, String p) {

        /**
         * 滑动窗口
         * 动态的改变窗口的长度，而不是始终固定，可以保留之前记录的字符个数而不用每次都重复记录
         * 将p中字符出现的次数保存在对应的ASCII码数组中，同时在遍历时记录下s中窗口的字符出现的次数，然后进行比较
         */
        int left = 0;
        int right = 0;
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        List list = new ArrayList();

        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
        }

        while (left < s.length() - p.length() + 1) {

            /**
             * 只要窗口长度小于p的长度，right就一直移动
             */
            if (right - left + 1 <= p.length()) {
                sCount[s.charAt(right) - 'a']++;
                right++;
            }
            else {

                /**
                 * 当长度相等时，判断当前的字符个数是否相等
                 */
                if (Arrays.equals(sCount, pCount)){
                    list.add(left);
                }

                /**
                 * 无论是否相等，left都要移动，同时要将上一个字符的次数减1
                 */
                sCount[s.charAt(left) - 'a']--;
                left++;
            }
        }

        return list;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/