哈希表高级应用（最小窗口子串 · 设计随机集合）

最小覆盖子串（LeetCode 76）

在 s 中找包含 t 所有字符的最短子串，滑动窗口 + 哈希：

String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

    int left = 0, right = 0;
    int valid = 0;  // 满足条件的字符种类数
    int start = 0, minLen = Integer.MAX_VALUE;

    while (right < s.length()) {
        char c = s.charAt(right++);
        if (need.containsKey(c)) {
            window.merge(c, 1, Integer::sum);
            if (window.get(c).equals(need.get(c))) valid++;
        }

        // 窗口已覆盖 t，收缩左边
        while (valid == need.size()) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            char d = s.charAt(left++);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.merge(d, -1, Integer::sum);
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

异位词的所有起始位置（LeetCode 438）

滑动窗口 + 频率匹配：

List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int[] pCount = new int[26], wCount = new int[26];
    for (char c : p.toCharArray()) pCount[c - 'a']++;

    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        wCount[s.charAt(right) - 'a']++;
        if (right - left + 1 == p.length()) {
            if (Arrays.equals(wCount, pCount)) result.add(left);
            wCount[s.charAt(left++) - 'a']--;
        }
    }
    return result;
}

O(1) 时间插入、删除和获取随机元素（LeetCode 380）

哈希表 + 动态数组：

class RandomizedSet {
    private final Map<Integer, Integer> map = new HashMap<>();  // val → index
    private final List<Integer> list = new ArrayList<>();
    private final Random rand = new Random();

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int idx = map.get(val);
        int last = list.get(list.size() - 1);
        // 将最后一个元素放到被删除位置
        list.set(idx, last);
        map.put(last, idx);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

关键：删除时用最后元素填补空缺，避免数组整体移位，保证 O(1)。

哈希表实现 LRU（见链表章）

哈希表 + 双向链表 → LRU 缓存，参见链表章节 06-lru-lfu.md。

单词规律（LeetCode 290）

双向映射：

boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) return false;
    Map<Character, String> charToWord = new HashMap<>();
    Map<String, Character> wordToChar = new HashMap<>();
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        String w = words[i];
        if (charToWord.containsKey(c) && !charToWord.get(c).equals(w)) return false;
        if (wordToChar.containsKey(w) && wordToChar.get(w) != c) return false;
        charToWord.put(c, w);
        wordToChar.put(w, c);
    }
    return true;
}