哈希表算法详解

哈希表（Hash Table）是一种通过键值对快速查找数据的数据结构，平均时间复杂度为 O(1)。

一、什么是哈希表

哈希表就像一个字典，给定一个「键」，能瞬间找到对应的「值」。

需求：在数组中找出两个数，使它们的和等于目标值

数组：[2, 7, 11, 15]，目标值：9

暴力解法：两层 for 循环，遍历所有组合
时间复杂度：O(n²)

哈希表解法：一边遍历一边记录
时间复杂度：O(n)

核心思想：

• 遍历数组时，把已经遍历过的数字和它的下标存入哈希表
• 当遍历到新数字时，检查哈希表中是否存在 目标值 - 当前数字
• 存在则找到答案，不存在则继续遍历

二、实战例题

2.1 两数之和

import java.util.HashMap;

public class TwoSum {

  public static int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> hashTable = new HashMap<>();
    int[] res = new int[2];

    for (int i = 0; i < nums.length; i++) {
      // 在哈希表中查找 target - 当前数
      if (hashTable.containsKey(target - nums[i])) {
        res[0] = hashTable.get(target - nums[i]);  // 找到之前存的下标
        res[1] = i;                                // 当前下标
      }
      // 把当前数字和下标存入哈希表
      hashTable.put(nums[i], i);
    }

    return res;
  }

  // 测试
  public static void main(String[] args) {
    int[] nums = {2, 7, 11, 15};
    int target = 9;
    // 输出: [0, 1]
  }
}

理解要点：

• 一边遍历一边存，存的是「之前遍历过的数字」
• 查找的是「当前数字的搭档」是否在哈希表中
• 找到后直接返回，不用继续遍历

2.2 字母异位词分组

题目： 将字母相同但顺序不同的单词分到一组

输入：["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["eat","tea","ate"], ["tan","nat"], ["bat"]]

核心思路： 把单词按字母排序后作为 key，相同的 key 就是异位词

import java.util.*;

public class GroupAnagrams {

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

    for (String str : strs) {
      // 1. 将单词按字母排序，统一格式
      char[] arr = str.toCharArray();
      Arrays.sort(arr);
      String key = String.valueOf(arr);

      // 2. 以排序后的单词作为 key 存入哈希表
      // computeIfAbsent：key 不存在时创建新 List
      map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
    }

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

理解要点：

• 异位词排序后相同，这是不变的规律
• 用排序后的结果作为 key，天然去重

2.3 最长连续序列

题目： 找出数组中最长连续数字序列的长度

输入：[100, 4, 200, 1, 3, 2]
输出：4
解释：最长序列是 [1, 2, 3, 4]

核心思路： 用哈希表存储已遍历的数字，快速判断某个数字的邻居是否存在

import java.util.*;

public class LongestConsecutive {

  public static int longestConsecutive(int[] nums) {
    if (nums == null || nums.length == 0) return 0;

    // 1. 用 HashSet 去重
    HashSet<Integer> hashSet = new HashSet<>();
    for (int num : nums) {
      hashSet.add(num);
    }

    int res = 0;
    ArrayList<Integer> arr = new ArrayList<>();

    // 2. 遍历每个数字
    for (Integer num : hashSet) {
      // 只从「序列起点」开始计算
      // 起点定义：num-1 不存在
      if (!hashSet.contains(num - 1)) {
        res = 1;
        int curIndex = num;

        // 3. 往后找连续的数
        while (hashSet.contains(curIndex + 1)) {
          res++;
          curIndex++;
        }

        arr.add(res);
      }
    }

    return arr.stream().max(Integer::compareTo).get();
  }
}

理解要点：

• 不是每个数字都当作起点
• 只有 num-1 不存在时，才是新序列的起点
• 这样避免了重复计算

2.4 和为 K 的子数组

题目： 统计和为 K 的连续子数组个数

输入：[1, 2, 3], K = 3
输出：2
解释：[1,2] 和 [3]

核心思路： 前缀和 + 哈希表统计出现次数

import java.util.HashMap;

public class SubarraySum {

  public static int subarraySum(int[] nums, int k) {
    int ans = 0, sum = 0;
    HashMap<Integer, Integer> hashMap = new HashMap<>();

    // 初始化：前缀和为 0 出现 1 次
    hashMap.put(0, 1);

    for (int i = 0; i < nums.length; i++) {
      // 1. 计算当前前缀和
      sum += nums[i];

      // 2. 查找是否存在 sum - k 的前缀和
      // 如果存在，说明中间这段子数组的和为 k
      if (hashMap.containsKey(sum - k)) {
        ans += hashMap.get(sum - k);
      }

      // 3. 记录当前前缀和出现的次数
      hashMap.put(sum, hashMap.getOrDefault(sum, 0) + 1);
    }

    return ans;
  }
}

理解要点：

• 前缀和：数组前 i 个元素的和
• 前缀和[j] - 前缀和[i] = k 等价于「从 i+1 到 j 的子数组和为 k」
• 用哈希表记录每个前缀和出现的次数

三、总结

题目	哈希表的作用
两数之和	存储已遍历的元素，快速查找目标值
字母异位词	以排序结果作为 key，分组
最长连续序列	去重 + 快速判断元素是否存在
和为 K 的子数组	存储前缀和出现的次数

哈希表适用场景：

• 需要快速查找某个元素是否存在
• 需要用某个值作为「分类依据」
• 需要统计元素出现的次数