Javajava算法
哈希表经典算法题整理
8 道经典的哈希表算法题，涵盖两数之和、无重复字符最长子串、字母异位词分组等。通过 Java 语言实现，详细展示了 HashMap、HashSet 及数组模拟哈希表的应用场景。内容包括题目描述、带注释代码、解题思路及复杂度分析。重点讲解了如何利用哈希表快速查找、判重、统计计数及分组聚合，替代暴力法优化时间复杂度至 O(n)。适合准备面试或提升算法能力的开发者阅读。
8 道经典的哈希表算法题，涵盖两数之和、无重复字符最长子串、字母异位词分组等。通过 Java 语言实现，详细展示了 HashMap、HashSet 及数组模拟哈希表的应用场景。内容包括题目描述、带注释代码、解题思路及复杂度分析。重点讲解了如何利用哈希表快速查找、判重、统计计数及分组聚合，替代暴力法优化时间复杂度至 O(n)。适合准备面试或提升算法能力的开发者阅读。
给定一个整数数组 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 - 当前元素（即需要找的补数）；给定一个字符串 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，提升效率）；给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 说明：字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
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]]
}
}
给你一个整数数组 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
}
}
给你一个 非空 整数数组 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
}
}
给定两个字符串 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
}
}
给定一个字符串 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
}
}
给定一个段落 (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
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online