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

题目描述

思路：滑动窗口模板

• 需要维护的变量：

// 1. 用于存放结果
List<Integer> res = new ArrayList<>();
// 2. 定义需要维护的变量:根据题意可知是一个哈希表
Map<Character, Integer> map = new HashMap<>();

Map<Character, Integer> hashmap_p = new HashMap<>();
for (char ch : p.toCharArray()) {
	hashmap_p.put(ch, hashmap_p.getOrDefault(ch, 0) + 1);
}

• 窗口长度为固定，所以用if：

 if (end >= p.length() - 1) {
// 或者 if (end - start + 1 == p.length()) {} 
	char startChar = s.charAt(start);
	map.put(startChar, map.get(startChar) - 1);
	if (map.get(startChar) == 0) {
		map.remove(startChar);
	}
	start ++;
}

类似LeetCode643. 子数组最大平均数I

方法一：滑动窗口

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 1. 用于存放结果
        List<Integer> res = new ArrayList<>();
        // 2. 定义需要维护的变量:根据题意可知是一个哈希表
        Map<Character, Integer> map = new HashMap<>();

        Map<Character, Integer> hashmap_p = new HashMap<>();
        for (char ch : p.toCharArray()) {
            hashmap_p.put(ch, hashmap_p.getOrDefault(ch, 0) + 1);
        }

        // 3. 定义窗口区间范围
        int start = 0;
        for (int end = 0; end < s.length(); end ++) {
            // 4. 更新需要维护的变量
            char currentChar = s.charAt(end);
            map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
            if (map.equals(hashmap_p)) {
                res.add(start);
            }

            // 5. 由题意知:窗口固定用if
            if (end >= p.length() - 1) {
                char startChar = s.charAt(start);
                map.put(startChar, map.get(startChar) - 1);
                if (map.get(startChar) == 0) {
                    map.remove(startChar);
                }
                start ++;
            }
        }
        return res;
    }
}

方法二：跟方法一在最后一个if中处理不同

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 1. 用于存放结果
        List<Integer> res = new ArrayList<>();
        // 2. 定义需要维护的变量:根据题意可知是一个哈希表
        Map<Character, Integer> map = new HashMap<>();

        Map<Character, Integer> hashmap_p = new HashMap<>();
        for (char ch : p.toCharArray()) {
            hashmap_p.put(ch, hashmap_p.getOrDefault(ch, 0) + 1);
        }

        // 3. 定义窗口区间范围
        int start = 0;
        for (int end = 0; end < s.length(); end ++) {
            // 4. 更新需要维护的变量
            char currentChar = s.charAt(end);
            map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
            if (map.equals(hashmap_p)) {
                res.add(start);
            }

            // 5. 由题意知:窗口固定用if
            if (end - start + 1 == p.length()) {
                char startChar = s.charAt(start);
                map.put(startChar, map.get(startChar) - 1);
                if (map.get(startChar) == 0) {
                    map.remove(startChar);
                }
                start ++;
            }
        }
        return res;
    }
}