Day 5：哈希表应用（两数之和、重复元素判断）
一、哈希表（Hash Table）基础
1. 什么是哈希表？
哈希表（Hash Table） 是一种键值对（key-value）存储的数据结构，它通过 哈希函数（Hash Function） 将键（Key）映射到数组中的索引，从而实现 快速查找、插入和删除，平均时间复杂度为 O(1)。
在 Java 中，哈希表主要通过 HashMap、HashSet 来实现：
- HashMap<K, V>：用于存储键值对，支持快速查找和修改
- HashSet<E>：用于存储唯一元素，支持快速去重和存在性查询
哈希表的优势 ✅ 查找、插入、删除速度快 O(1)
✅ 适用于频繁查找的场景（如词频统计、数据去重、映射关系存储）
二、练习 1：两数之和（Two Sum）
1. 题目描述
给定一个整数数组 nums 和一个目标值 target，请找出 数组中和为 target 的两个数的索引，假设只有唯一答案。
示例
输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1] （因为 nums[0] + nums[1] = 2 + 7 = 9）
2. 暴力解法（O(n²)）
public class TwoSumBruteForce {
public static int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j}; // 找到答案返回索引
}
}
}
return new int[]{}; // 没找到返回空数组
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("索引: " + result[0] + ", " + result[1]); // 输出 0, 1
}
}
❌ 缺点：
- 时间复杂度 O(n²)，遍历所有可能的数对，效率低
- 适用于小规模数据，但大数据情况下会超时
3. 优化解法：使用 HashMap（O(n)）
我们可以使用 哈希表存储已经遍历过的数字，这样可以在 O(1) 时间复杂度内找到需要的另一个数：
- 遍历数组 nums，计算 需要的数 = target - nums[i]
- 如果 HashMap 里已经存有 需要的数，则返回索引
- 否则，将 nums[i] 存入 HashMap，继续遍历
import java.util.HashMap;
public class TwoSumHashMap {
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); // 存入哈希表
}
return new int[]{}; // 没找到
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("索引: " + result[0] + ", " + result[1]); // 输出 0, 1
}
}
✅ 优点
- 时间复杂度：O(n)，遍历数组一次即可
- 空间复杂度：O(n)，哈希表最多存储 n 个元素
三、练习 2：存在重复元素（Contains Duplicate）
1. 题目描述
给定一个整数数组 nums，如果数组中存在重复元素，返回 true，否则返回 false。
示例
输入: nums = [1,2,3,1]
输出: true
输入: nums = [1,2,3,4]
输出: false
2. 暴力解法（O(n²)）
public class ContainsDuplicateBruteForce {
public static boolean containsDuplicate(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return true; // 找到重复元素
}
}
}
return false;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1};
System.out.println(containsDuplicate(nums)); // 输出 true
}
}
❌ 缺点：
- 时间复杂度 O(n²)，需要遍历所有可能的数对，性能较差
3. 优化解法：使用 HashSet（O(n)）
我们可以使用 哈希集合 HashSet 来存储遍历过的元素，如果在遍历时发现某个元素已经存在于 Set 中，则说明有重复元素。
import java.util.HashSet;
public class ContainsDuplicateHashSet {
public static boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>(); // 存储已访问的元素
for (int num : nums) {
if (set.contains(num)) {
return true; // 找到重复元素
}
set.add(num); // 添加新元素
}
return false;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1};
System.out.println(containsDuplicate(nums)); // 输出 true
}
}
✅ 优点
- 时间复杂度 O(n)，每个元素只需检查 HashSet 一次
- 空间复杂度 O(n)，HashSet 最多存储 n 个元素
四、总结
问题 |
暴力解法 |
优化解法 |
时间复杂度 |
两数之和 |
O(n²) 双重循环 |
O(n) 使用 HashMap |
O(n) |
是否包含重复元素 |
O(n²) 双重循环 |
O(n) 使用 HashSet |
O(n) |
五、哈希表应用场景
✅ 查找问题（两数之和、存在重复元素、字母异位词）
✅ 去重问题（统计唯一值、去重操作）
✅ 数据映射（存储键值对，如电话号码簿）
六、易错点
1. 哈希表的初始化
在使用 HashMap 或 HashSet 时，要确保正确初始化，避免出现空指针异常。
2. 键的唯一性
要注意哈希表中键的唯一性，如果需要记录元素出现的次数，不能简单地使用 HashSet，而应该使用 HashMap 来记录元素及其出现的次数。
3. 哈希函数的理解
虽然 Java 中不需要手动实现哈希函数，但对于哈希函数的基本原理和作用要有一定的理解，以便在遇到相关问题时能够正确分析。
4. 边界条件处理
在处理具体问题时，要考虑数组为空、只有一个元素等边界情况，确保代码的健壮性。