1. 力扣 1 - 两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。 注意：只会存在一个有效答案。
带注释代码
import java.util.HashMap;
/**
* 力扣 1 - 两数之和
*/
public class E01Leetcode1 {
public int[] twoSum(int[] nums, int target) {
// 哈希表：key=数组元素值，value=元素对应的下标
HashMap<Integer, Integer> map = new HashMap<>();
// 遍历数组，逐个处理元素
for (int i = 0; i < nums.length; i++) {
int current = nums[i]; // 当前遍历到的元素
int complement = target - current; // 目标值与当前元素的差值（需要找的另一个数）
// 检查哈希表中是否存在这个差值：存在则找到答案，不存在则存入当前元素
if (map.containsKey(complement)) {
// 找到差值，返回当前下标 和 差值对应的下标
return new int[]{i, map.get(complement)};
} else {
// 未找到差值，将当前元素和下标存入哈希表
map.put(current, i);
}
}
// 题目保证有解，此处仅为语法兜底
return null;
}
}
解题思路
- 核心思想：用哈希表存储已遍历元素的「值 - 下标」映射，将「找两个数之和」转化为「找当前数的补数是否已出现」，降低时间复杂度；
- 步骤拆解：
- 遍历数组，对每个元素计算
target - 当前元素（即需要找的补数）； - 检查哈希表中是否存在该补数：存在则直接返回两个数的下标，不存在则将当前元素和下标存入哈希表；
- 遍历数组，对每个元素计算
- 复杂度：时间 O(n)（仅遍历一次数组），空间 O(n)（哈希表最多存储 n-1 个元素）；
- 哈希表作用：快速查找补数是否存在，替代暴力法的双层循环。
2. 力扣 3 - 无重复字符的最长子串
题目描述
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。 说明：s 由英文字母、数字、符号和空格组成。
带注释代码
import java.util.Arrays;
/**
* 力扣 3 - 无重复字符的最长子串
*/
public class E02Leetcode3 {
public int lengthOfLongestSubstring(String s) {
// 用数组模拟哈希表（ASCII 码范围 0-127），存储字符最后一次出现的下标，初始值 -1 表示未出现
int[] charIndexMap = new int[128];
Arrays.fill(charIndexMap, -1);
int left = 0; // 滑动窗口左边界（无重复子串的起始位置）
int maxLen = 0; // 记录最长无重复子串长度
// 滑动窗口右边界遍历字符串
for (int right = 0; right < s.length(); right++) {
char currentChar = s.charAt(right); // 当前字符
int lastIndex = charIndexMap[currentChar]; // 当前字符最后一次出现的下标
// 若字符已出现过，且最后一次出现位置在窗口内 → 调整左边界到「最后一次出现位置 +1」
if (lastIndex != -1) {
left = Math.max(left, lastIndex + 1);
}
// 更新当前字符的最后出现位置为当前右边界
charIndexMap[currentChar] = right;
// 计算当前窗口长度，更新最大长度（窗口长度=右边界 - 左边界 +1）
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
public static void main(String[] args) {
E02Leetcode3 solution = new E02Leetcode3();
System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); // 输出 3
System.out.println(solution.lengthOfLongestSubstring("abca")); // 输出 3
}
}
解题思路
- 核心思想：滑动窗口 + 数组模拟哈希表，用窗口维护「无重复子串」范围，用哈希表快速判断字符是否重复；
- 步骤拆解：
- 用
left和right表示滑动窗口的左右边界，窗口内始终是无重复子串； - 数组
charIndexMap存储每个字符最后一次出现的下标（替代 HashMap，提升效率）； - 右边界遍历字符：若字符已在窗口内重复，将左边界移动到「重复字符最后出现位置 +1」；
- 每次遍历更新字符最后出现位置，并计算当前窗口长度，更新最大值；
- 用
- 复杂度：时间 O(n)（仅遍历一次字符串），空间 O(1)（数组大小固定为 128）；
- 哈希表作用：O(1) 时间查询字符最后出现位置，避免遍历窗口判断重复。
3. 力扣 49 - 字母异位词分组
题目描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 说明：字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
带注释代码
import java.util.*;
/**
* 力扣 49 - 字母异位词分组
*/
public class E03Leetcode49 {
// 自定义哈希 Key：用 26 位数组统计字符出现次数，重写 equals 和 hashCode 保证哈希表正确性
static class CharCountKey {
int[] count = new int[26]; // 对应 a-z 的字符计数
// 构造器：根据字符串生成字符计数数组
public CharCountKey(String str) {
for (char ch : str.toCharArray()) {
count[ch - 'a']++; // 'a'对应下标 0，统计每个字符出现次数
}
}
// 重写 equals：字符计数数组相同则视为相等（字母异位词）
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
CharCountKey that = (CharCountKey) o;
return Arrays.equals(count, that.count);
}
// 重写 hashCode：基于字符计数数组生成哈希值
@Override
public int hashCode() {
return Arrays.hashCode(count);
}
}
// 解法 1：自定义 Key（字符计数数组）
public List<List<String>> groupAnagrams(String[] strs) {
// 哈希表：key=字符计数特征，value=该特征对应的所有字母异位词
HashMap<CharCountKey, List<String>> map = new HashMap<>();
for (String str : strs) {
CharCountKey key = new CharCountKey(str);
// 若 Key 不存在则新建 List，存在则获取已有 List（简化判空逻辑）
List<String> group = map.computeIfAbsent(key, k -> new ArrayList<>());
group.add(str); // 将当前字符串加入对应分组
}
// 将哈希表的值（所有分组）转为 List 返回
return new ArrayList<>(map.values());
}
// 解法 2：排序字符串作为 Key（更简洁）
public List<List<String>> groupAnagrams1(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars); // 字母异位词排序后字符串相同
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> result = new E03Leetcode49().groupAnagrams(strs);
System.out.println(result); // 输出：[[eat, tea, ate], [tan, nat], [bat]]
}
}
解题思路
- 核心思想：提取字母异位词的「唯一特征」作为哈希表 Key，将特征相同的字符串归为一组；
- 特征提取方式：
- 方式 1（自定义 Key）：用 26 位数组统计每个字符出现次数，数组相同则为字母异位词（需重写 equals/hashCode）；
- 方式 2（排序 Key）：将字符串字符排序，字母异位词排序后结果相同；
- 步骤拆解：
- 遍历字符串数组，为每个字符串生成唯一特征 Key；
- 用哈希表存储「Key-字符串列表」映射，将同特征字符串加入同一列表；
- 最终返回哈希表中所有列表；
- 复杂度：时间 O(nk)（n 为字符串数量，k 为字符串长度），空间 O(nk)；
- 哈希表作用：按特征分组，快速聚合字母异位词。
4. 力扣 217 - 存在重复元素
题目描述
给你一个整数数组 nums。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素都互不相同，返回 false。
带注释代码
import java.util.HashMap;
import java.util.HashSet;
/**
* 力扣 217 - 存在重复元素
*/
public class E04Leetcode217 {
// 解法 1：HashMap 实现
public boolean containsDuplicate1(int[] nums) {
// 哈希表：key=数组元素，value=占位符（仅用于判断存在性）
HashMap<Integer, Object> map = new HashMap<>(nums.length * 2);
Object placeholder = new Object();
for (int num : nums) {
// put 方法返回旧值：非 null 表示元素已存在，直接返回 true
Object oldValue = map.put(num, placeholder);
if (oldValue != null) {
return true;
}
}
return false;
}
// 解法 2：HashSet 实现（更简洁）
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
// add 方法返回 false 表示元素已存在，直接返回 true
if (!set.add(num)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
E04Leetcode217 solution = new E04Leetcode217();
System.out.println(solution.containsDuplicate(new int[]{1, 2, 3, 1})); // 输出 true
System.out.println(solution.containsDuplicate(new int[]{1, 2, 3, 4})); // 输出 false
}
}
解题思路
- 核心思想：利用哈希表/集合的「元素唯一性」特性，遍历数组时判断元素是否已存在；
- 步骤拆解：
- 解法 1（HashMap）：遍历数组，用 put 方法存储元素，若返回旧值则说明元素重复；
- 解法 2（HashSet）：遍历数组，用 add 方法添加元素，若返回 false 则说明元素重复；
- 只要发现重复元素，立即返回 true，遍历结束未发现则返回 false；
- 复杂度：时间 O(n)，空间 O(n)；
- 哈希表作用：O(1) 时间判断元素是否已出现，替代暴力法的双层循环。
5. 力扣 136 - 只出现一次的数字
题目描述
给你一个 非空 整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 要求：实现线性时间复杂度、不使用额外空间的解法（位运算），也可实现哈希表解法。
带注释代码
import java.util.HashSet;
/**
* 力扣 136 - 只出现一次的数字
*/
public class E05Leetcode136 {
// 解法 1：位运算（异或）- 最优解（空间 O(1)）
public int singleNumber(int[] nums) {
int result = nums[0]; // 异或特性：相同数字异或=0，0 异或任何数=数本身
for (int i = 1; i < nums.length; i++) {
result ^= nums[i];
}
return result;
}
// 解法 2：HashSet 实现
public int singleNumber1(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
// add 返回 false 表示元素已存在 → 移除该元素；返回 true 表示首次出现 → 保留
if (!set.add(num)) {
set.remove(num);
}
}
// 最终集合中仅存唯一出现一次的元素
return set.toArray(new Integer[0])[0];
}
public static void main(String[] args) {
E05Leetcode136 solution = new E05Leetcode136();
System.out.println(solution.singleNumber1(new int[]{2, 2, 1})); // 输出 1
System.out.println(solution.singleNumber(new int[]{4, 1, 2, 1, 2})); // 输出 4
}
}
解题思路
解法 1（位运算）
- 核心思想：利用异或运算的特性：
- 相同数字异或结果为 0（如 2^2=0）；
- 0 异或任何数字结果为数字本身（如 0^1=1）；
- 步骤：遍历数组，将所有元素依次异或，最终结果即为唯一出现一次的数字；
- 复杂度：时间 O(n)，空间 O(1)。
解法 2（HashSet）
- 核心思想：利用集合的唯一性，「出现两次的元素添加后又移除，仅保留出现一次的元素」；
- 步骤：
- 遍历数组，添加元素到集合：add 返回 false（已存在）则移除，返回 true（首次出现）则保留；
- 最终集合中仅剩唯一元素；
- 复杂度：时间 O(n)，空间 O(n)；
- 哈希表作用：记录元素出现次数（通过添加/移除实现「出现偶数次则删除」）。
6. 力扣 242 - 有效的字母异位词
题目描述
给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。 说明：假设字符串只包含小写字母。
带注释代码
import java.util.Arrays;
/**
* 力扣 242 - 有效的字母异位词
*/
public class E06Leetcode242 {
public boolean isAnagram(String s, String t) {
// 若长度不同，直接不是字母异位词
if (s.length() != t.length()) {
return false;
}
// 分别生成两个字符串的字符计数数组，比较是否相同
return Arrays.equals(getCharCount(s), getCharCount(t));
}
// 生成字符计数数组：统计每个小写字母出现次数
private int[] getCharCount(String str) {
int[] countArray = new int[26]; // 对应 a-z
for (char ch : str.toCharArray()) {
countArray[ch - 'a']++; // 'a'对应下标 0，统计次数
}
return countArray;
}
public static void main(String[] args) {
E06Leetcode242 solution = new E06Leetcode242();
System.out.println(solution.isAnagram("anagram", "nagaram")); // 输出 true
System.out.println(solution.isAnagram("rat", "car")); // 输出 false
}
}
解题思路
- 核心思想：字母异位词的核心特征是「每个字符出现次数完全相同」，用数组模拟哈希表统计次数；
- 步骤拆解：
- 先判断两个字符串长度是否相同：不同则直接返回 false；
- 分别生成两个字符串的字符计数数组（26 位，对应 a-z）；
- 比较两个数组是否相同：相同则为字母异位词；
- 复杂度：时间 O(n)（n 为字符串长度），空间 O(1)（数组大小固定为 26）；
- 哈希表作用：统计字符出现次数，快速对比两个字符串的字符分布。
7. 力扣 387 - 字符串中的第一个唯一字符
题目描述
给定一个字符串 s，找到 它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 说明：s 只包含小写英文字母。
带注释代码
/**
* 力扣 387 - 字符串中的第一个唯一字符
*/
public class E07Leetcode387 {
public int firstUniqChar(String s) {
// 数组模拟哈希表：统计每个小写字母出现的次数
int[] charCount = new int[26];
char[] chars = s.toCharArray();
// 第一次遍历：统计所有字符出现次数
for (char ch : chars) {
charCount[ch - 'a']++;
}
// 第二次遍历：找到第一个出现次数为 1 的字符，返回其下标
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
if (charCount[ch - 'a'] == 1) {
return i;
}
}
// 无唯一字符，返回 -1
return -1;
}
public static void main(String[] args) {
E07Leetcode387 solution = new E07Leetcode387();
System.out.println(solution.firstUniqChar("leetcode")); // 输出 0
System.out.println(solution.firstUniqChar("loveleetcode")); // 输出 2
System.out.println(solution.firstUniqChar("aabb")); // 输出 -1
}
}
解题思路
- 核心思想：两次遍历 + 数组模拟哈希表，第一次统计次数，第二次找首个次数为 1 的字符；
- 步骤拆解：
- 第一次遍历：用 26 位数组统计每个字符的出现次数；
- 第二次遍历：按字符串顺序检查字符次数，第一个次数为 1 的字符即为答案；
- 复杂度：时间 O(n)（两次遍历字符串），空间 O(1)；
- 哈希表作用：快速统计字符出现次数，避免逐个字符对比的暴力法。
8. 力扣 819 - 最常见的单词
题目描述
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多的、不在禁用列表中的单词。 说明：
- 题目保证至少有一个词不在禁用列表中，且答案唯一；
- 段落中的单词不区分大小写，答案返回小写形式。
带注释代码
import java.util.*;
/**
* 力扣 819 - 最常见的单词
*/
public class E08Leetcode819 {
// 最优解法：字符遍历（避免 split 的性能损耗）
public String mostCommonWord(String paragraph, String[] banned) {
// 禁用词集合：O(1) 时间判断是否为禁用词
Set<String> bannedSet = Set.of(banned);
// 哈希表：key=单词，value=出现次数
HashMap<String, Integer> wordCount = new HashMap<>();
char[] chars = paragraph.toLowerCase().toCharArray();
StringBuilder sb = new StringBuilder(); // 拼接当前单词
// 遍历字符，提取单词并统计次数
for (char ch : chars) {
// 是小写字母则拼接，否则处理当前单词
if (ch >= 'a' && ch <= 'z') {
sb.append(ch);
} else {
String word = sb.toString();
// 非禁用词且单词非空，统计次数
if (!bannedSet.contains(word) && !word.isEmpty()) {
wordCount.compute(word, (k, v) -> v == null ? 1 : v + 1);
}
sb.setLength(0); // 清空字符串构建器
}
}
// 处理最后一个单词（段落末尾无分隔符的情况）
if (sb.length() > 0) {
String word = sb.toString();
if (!bannedSet.contains(word)) {
wordCount.compute(word, (k, v) -> v == null ? 1 : v + 1);
}
}
// 遍历哈希表，找到出现次数最多的单词
int maxCount = 0;
String result = null;
for (Map.Entry<String, Integer> entry : wordCount.entrySet()) {
int count = entry.getValue();
if (count > maxCount) {
maxCount = count;
result = entry.getKey();
}
}
return result;
}
public static void main(String[] args) {
E08Leetcode819 solution = new E08Leetcode819();
String paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
String[] banned = {"hit"};
System.out.println(solution.mostCommonWord(paragraph, banned)); // 输出 ball
}
}
解题思路
- 核心思想：字符遍历提取单词 + 哈希表统计次数 + 禁用词集合快速过滤；
- 步骤拆解：
- 将段落转为小写，遍历字符拼接单词（避免 split 正则的性能损耗）；
- 用 HashSet 存储禁用词，O(1) 时间判断单词是否禁用；
- 用 HashMap 统计非禁用词的出现次数；
- 遍历哈希表，找到次数最多的单词；
- 复杂度：时间 O(n)（n 为段落长度），空间 O(m)（m 为非禁用词数量）；
- 哈希表作用：
- HashSet：快速过滤禁用词；
- HashMap：统计单词出现次数，快速查找次数最大值。
总结
哈希表在这些题目中的核心应用场景
- 快速查找/判重：两数之和、存在重复元素（O(1) 时间判断元素是否存在）；
- 统计计数：字母异位词、第一个唯一字符、最常见单词（统计字符/单词出现次数）；
- 分组聚合：字母异位词分组（按特征聚合同类元素）；
- 记录位置/状态：无重复最长子串（记录字符最后出现位置）；
- 替代暴力循环：所有题目均通过哈希表将暴力法的 O(n²) 时间复杂度优化为 O(n)。
哈希表实现技巧
- 数组模拟哈希表：针对小写字母（26 位）、ASCII 字符（128 位），效率高于 HashMap；
- HashSet 简化判重：无需存储值时，用 HashSet 替代 HashMap；
- computeIfAbsent 简化逻辑：避免手动判空 + 新建集合/赋值；
- 自定义 Key：需重写 equals 和 hashCode，保证哈希表正确性。
