LeetCode 438. 找到字符串中所有字母异位词 [Hot 100]

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

已解答

中等

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路不难，注意两个关键点：

1.注意map里存的是Integer不是int，要使用equals比较Integer值，避免自动装箱带来的问题

2.map.put(ch, map.getOrDefault(ch, 0) + 1);可以减少判断key是否存在

class Solution {
    private boolean check(Map<Character, Integer> map, Map<Character, Integer> map1) {
        // 先检查大小是否一致，提高效率
        if (map.size() != map1.size()) return false;
        
        for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            // 使用equals比较Integer值，避免自动装箱带来的问题
            if (!map.containsKey(key) || !map.get(key).equals(value)) {
                return false;
            }
        }
        return true;
    }
    
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> map1 = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        int n1 = s.length();
        int n2 = p.length();
        
        if (n1 < n2) return ans;
        
        // 初始化p的字符计数map1
        for (int i = 0; i < n2; i++) {
            char ch1 = p.charAt(i);
            map1.put(ch1, map1.getOrDefault(ch1, 0) + 1);
        }
        
        // 初始化第一个窗口的字符计数map
        for (int i = 0; i < n2; i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        
        // 检查初始窗口
        if (check(map, map1)) {
            ans.add(0);
        }
        
        // 滑动窗口
        for (int i = n2; i < n1; i++) {
            // 添加新字符
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
            
            // 移除窗口最左侧字符
            char ch1 = s.charAt(i - n2);
            int count = map.get(ch1);
            if (count == 1) {
                map.remove(ch1);
            } else {
                map.put(ch1, count - 1);
            }
            
            // 检查当前窗口
            if (check(map, map1)) {
                ans.add(i - n2 + 1);
            }
        }
        
        return ans;
    }
}