LeetCode高频算法解题套路-哈希表

发表于 2025-04-21 更新于 2025-05-14 分类于 LeetCode高频算法解题套路阅读次数：

哈希表（Hash Table）在 LeetCode 算法题中极其重要，是最常见、最高频的数据结构之一，其适用范围广，解决问题高效。

1. 哈希表适用场景与核心使用技巧

哈希表是一种基于“键值对”设计的数据结构，具有插入、查找、删除操作平均 O(1) 的特性，适合处理以下几类高频问题：

场景分类	应用说明	常用结构	典型题目
存在性查找	判断元素是否出现过	`HashSet`	217. 存在重复元素 349. 两数组交集
频次统计	统计元素出现次数	`HashMap<T, Integer>`	242. 有效的字母异位词 347. 前 K 个高频元素
映射关系	元素与索引/字符等映射	`HashMap<K, V>`	1. 两数之和 205. 同构字符串
滑动窗口(已写)	窗口内状态记录	`Map<Character, Integer>`	3. 无重复字符的最长子串 76. 最小覆盖子串
前缀和	子数组和统计	`Map<Integer, Integer>`	560. 和为 K 的子数组
分组归类	根据规则分组	`Map<String, List<T>>`	49. 字母异位词分组
缓存设计	设计 LRU/LFU	`LinkedHashMap` + 自定义链表	146. LRU 缓存

2. 典型题目精讲

2.1 存在性查找

LeetCode - 217.存在重复元素

难度：简单

题目：给你一个整数数组 nums 。如果任一值在数组中出现至少两次，返回 true ；如果数组中每个元素互不相同，返回 false 。

解题思路：

借助 HashSet 元素不可重复 的特性，遍历数组将元素逐个插入 HashSet。

当元素重复时 .add(E e) 会返回 false，反之 .add(E e) 始终为 true，说明没有重复元素。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int i : nums) {
            if (!numSet.add(i)) {   // 向HashSet中插入重复元素会返回 false
                return true;
            } 
        }
        return false;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

LeetCode - 349.两数组交集

难度：简单

题目：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

解题思路：

题目要对两个数组 求交集 && 结果元素唯一

用一个 HashSet 将 nums1 的元素全部存起来，这个过程完成了对 nums1 的去重
遍历 nums2 元素，判断其是否存在于 HashSet 及其结果集中

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {

        Set<Integer> set = new HashSet<>();
        Set<Integer> res = new HashSet<>();

      	// 对 nums1 去重
        for (int i : nums1) {
            set.add(i);
        }
				
      	// 找出交集 顺带用 HashSet完成去重
        for (int j : nums2) {
            if (set.contains(j)) {
                res.add(j);
            }
        }

      	// 转换数据类型
        int[] ans = new int[res.size()];
        int idx = 0;
        for (int k : res) {
            ans[idx++] = k;
        }

        return ans;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

2.2 频次统计

LeetCode - 242. 有效的字母异位词

难度：简单

题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。（s 和 t 仅包含小写字母）

解题思路：

该题目核心是统计每个字母出现的次数，结合 Java 字符类型 char 的特点，可以用 char - 'a' 作为下标。

所以我们只需要把 s 的出现次数全都统计出来，再遍历 t 看是否每个字符出现次数一致即可。

class Solution {
    public boolean isAnagram(String s, String t) {
			
      	// 字符串长度不相等 => false
        int sLen = s.length();
        int tLen = t.length();
        if (sLen != tLen) {
            return false;
        }
        
        int[] tbl = new int[26];

        for (int i = 0; i < sLen; i++) {
            tbl[s.charAt(i) - 'a']++;
        }

        for (int j = 0; j < tLen; j++) {
            int idx = t.charAt(j) - 'a';
            tbl[idx]--;
          	
          	// 因为方法开始判断了长度，所以不用担心 t 遍历完还存在 tbl[idx] > 0 的情况
            if (tbl[idx] < 0) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(1)

LeetCode - 347. 前 K 个高频元素

难度：中等

题目：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

解题思路：

首先统计所有数字出现的次数
不一定需要用到小顶堆，可以对 map.values() 排序找到最小次数，再遍历 map.keySet() 比较其 value

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        
        // 统计所有数字的出现次数
        Map<Integer, Integer> counter = new HashMap<>();
        for (int i : nums) {
            counter.put(i, counter.getOrDefault(i, 0) + 1);
        }

        // 小顶堆筛选前 k 个元素
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });

        for(Integer i : counter.keySet()) {
            int val = counter.get(i);
            if (pq.size() == k) {
                if (pq.peek()[1] < val) {
                    pq.poll();
                    pq.offer(new int[]{i, val});
                }
            } else {
                pq.offer(new int[]{i, val});
            }
        }

        // 数据类型转换
        int[] ans = new int[k];
        for (int i = 0; i < k; ++i) {
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

2.3 映射关系

LeetCode - 1.两数之和

难度：简单

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

解题思路：

把数组元素的值、下标分别作为HashMap 的 key、value
targer - nums[i] 作为预期值，使用 HashMap.containsKey() 判断预期值是否存在

class Solution {
    public int[] twoSum(int[] nums, int target) {

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

        return new int[0];
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

LeetCode - 205. 同构字符串

难度：简单

题目：如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

解题思路：

不太好描述，核心就是用两个 HashMap 分别记录两个字符串中每个字符，同时记录对方的字符，再遍历做交叉验证。

// LeetCode 官方解法
class Solution {
    public boolean isIsomorphic(String s, String t) {

        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();

        int len = s.length();
        for (int i = 0; i < len; ++i) {
            
            char x = s.charAt(i), y = t.charAt(i);

            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }

            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

2.4 滑动窗口

《LeetCode高频算法解题套路-双指针》

2.5 前缀和

LeetCode - 560. 和为 K 的子数组

难度：中等

题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

解题思路：

使用前缀和，遍历元素，挨个累加并记录到 HashMap
当遍历到 i 个元素时，检测 HashMap 中是否记录 pre - k，存在说明找到了满足条件的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        
        int count = 0, pre = 0;

        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];

            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }

            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }

        return count;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

2.6 分组归类

LeetCode - 49. 字母异位词分组

难度：中等

题目：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

解题思路：

将字符串转换为字符数组，并排序。
用一个 HashMap 记录，将排序后的字符串作为key，排序前的字符串作为 value

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            List<String> val = map.getOrDefault(key, new ArrayList<>());
            val.add(str);
            map.put(key, val);
        }

        return new ArrayList<>(map.values());
    }
}

复杂度分析：

时间复杂度：O(n * k log k)

空间复杂度：O(n * k)

2.7 缓存设计

LeetCode - 146. LFU 缓存

难度：中等

题目：请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。