在Java编程面试中，哈希表（Hash Table）是一个非常重要的数据结构，能够高效地解决许多问题。LeetCode中的Top 100题目中，许多涉及哈希表的题目都能帮助我们更好地理解这个数据结构的应用。本文将介绍一些经典的哈希表题目，并提供相应的代码示例。
一、哈希表的基本概念
哈希表是通过哈希函数将键映射到存储桶或者槽中，从而实现高效查找、插入和删除操作的数据结构。最常用的实现是通过数组和链表的结合。哈希表的平均时间复杂度为O(1)，然而在最坏情况下，查找和插入的时间复杂度为O(n)，这时所有的元素可能会被映射到同一个槽中。
二、经典题目示例
1. 两数之和（Two Sum）
问题描述：给定一个整数数组和一个目标值，在数组中找出和为目标值的两个数，并返回它们的索引。
代码示例：
import java.util.HashMap;
public class TwoSum {
public static int[] twoSum(int[] nums, int target) {
HashMap<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);
}
throw new IllegalArgumentException("No two sum solution");
}
}
解析：使用一个哈希表存储已经遍历的数组元素及其索引。在每次迭代中，计算目标值与当前元素的差值，检查该差值是否存在于哈希表中。如果存在，则返回该元素的索引和当前元素的索引。
2. 字母异位词分组（Group Anagrams）
问题描述：给定一个字符串数组，将所有字母异位词分到同一组。
代码示例：
import java.util.*;
public class GroupAnagrams {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortedStr = new String(charArray);
map.putIfAbsent(sortedStr, new ArrayList<>());
map.get(sortedStr).add(str);
}
return new ArrayList<>(map.values());
}
}
解析：将每个字符串转换为字符数组并排序，使得所有字母异位词的排序结果相同。然后利用哈希表将相同排序结果的字符串存入同一组中。
3. 无重叠区间（Non-overlapping Intervals）
问题描述：给定一个区间的集合，找到不重叠区间的最大数量。
代码示例：
import java.util.*;
public class NonOverlappingIntervals {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int count = 0;
int end = Integer.MIN_VALUE;
for (int[] interval : intervals) {
if (interval[0] >= end) {
end = interval[1];
} else {
count++;
}
}
return count;
}
}
解析：首先根据结束时间对区间进行排序。当遍历区间时，判断当前区间的起始时间是否大于或等于最后一个加入不重叠集合的区间的结束时间，如果是，则可以加入；如果不是，则需要增加冲突计数器。
三、总结
哈希表在解决问题时能够显著提高算法的效率。在面试中，考生除了要掌握哈希表的基本用法和常见题型外，还需要了解其时间复杂度以及适用场景。通过不断练习LeetCode上相关的题目，能够帮助我们更加熟练地使用这种数据结构，从而在面试中脱颖而出。希望本文能够帮助到即将参加Java面试的你！
