哈希表高频题型

哈希表的核心价值

用空间换时间：把 O(n) 的查找/去重变为 O(1)。

Java 常用操作：

// HashMap - 键值映射
Map<Integer, Integer> map = new HashMap<>();
map.put(key, value);
map.getOrDefault(key, 0);
map.containsKey(key);
map.merge(key, 1, Integer::sum);  // 出现次数统计

// HashSet - 去重/存在性判断
Set<Integer> set = new HashSet<>();
set.add(val);
set.contains(val);
set.remove(val);

计数类

存在重复元素（LeetCode 217）

boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int num : nums) {
        if (!seen.add(num)) return true;  // add 返回 false 表示已存在
    }
    return false;
}

字母异位词分组（LeetCode 49）

用排序后的字符串作 key，把所有异位词归到同一组：

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

也可以用字符频次数组（int[26]）作 key，避免排序：Arrays.toString(freq) 转字符串。

前 K 个高频元素（LeetCode 347）

统计频次 → 小根堆维护前 k 个：

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums) count.merge(n, 1, Integer::sum);

    // 小根堆（按频次排）
    PriorityQueue<Integer> pq = new PriorityQueue<>(
        (a, b) -> count.get(a) - count.get(b)
    );
    for (int key : count.keySet()) {
        pq.offer(key);
        if (pq.size() > k) pq.poll();  // 维护大小为 k
    }

    int[] res = new int[k];
    for (int i = k - 1; i >= 0; i--) res[i] = pq.poll();
    return res;
}

映射关系类

两数之和（LeetCode 1）

边遍历边查哈希表，比两层循环快：

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{};
}

同构字符串（LeetCode 205）

s[i] → t[i] 的映射必须是双射（一对一）：

boolean isIsomorphic(String s, String t) {
    Map<Character, Character> st = new HashMap<>();
    Map<Character, Character> ts = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        if (st.containsKey(a) && st.get(a) != b) return false;
        if (ts.containsKey(b) && ts.get(b) != a) return false;
        st.put(a, b);
        ts.put(b, a);
    }
    return true;
}

区间/连续性类

最长连续序列（LeetCode 128）

用 HashSet 存所有数，只从连续段的起点开始计数：

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);

    int res = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) {  // n 是连续段的起点
            int cur = n, len = 1;
            while (set.contains(cur + 1)) { cur++; len++; }
            res = Math.max(res, len);
        }
    }
    return res;
}

时间复杂度 O(n)：虽然有内层 while，但每个数只被访问一次（只从起点触发）。

选用建议