438. 找到字符串中所有字母异位词（滑动窗口）

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

• 题目
• 解题思路
• 代码

题目

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

• 字母异位词指字母相同，但排列不同的字符串。
• 不考虑答案输出的顺序。

解题思路

套模板，只要解决好

1. 扩大窗口时，即加入字符时，应更新哪些数据
2. 什么条件下收缩窗口
3. 收缩窗口，即移出字符时，应更新哪些数据
4. 要的结果是在扩大窗口还是在收缩窗口时候更新

代码

class Solution {
    public List<Integer> findAnagrams(String s1, String s2) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char c : s2.toCharArray()) {
            //取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int right = 0;
        int valid = 0;//窗口中已经满足need中条件的字符个数。
        List<Integer> res=new ArrayList<>();

        // 记录最小覆盖字串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s1.length()) {
            char c = s1.charAt(right);

            right++;
            //进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

/*本题缩小窗口的时机应该是窗口内已经出现了满足条件的子串。
因为各种排列的长度应该是相同的。s2.length()就是那个标准，因为找的是s2的全排列
*/
            while (right - left >= s2.length()) {
                //窗口符合条件，把起始索引加入res
                if (valid == need.size()) {
                    res.add(left);
                }
                char d = s1.charAt(left);
                left++;
                //进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);

                }
            }


        }
        return res;

    }
}