哈希

[!abstract] 本笔记收集 Hot 100 中与哈希相关的经典题目与 Java 解法。

快速导航

• [1. 两数之和](#1. 两数之和)
• [49. 字母异位词分组](#49. 字母异位词分组)
• [128. 最长连续序列](#128. 最长连续序列)

1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且不能使用两次相同的元素。

你可以按任意顺序返回答案。

答案代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        // key: 数组中的值，value: 数组下标
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];

            if (map.containsKey(complement)) {
                return new int[]{i, map.get(complement)};
            }

            map.put(nums[i], i);
        }

        return new int[0];
    }
}

49. 字母异位词分组

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

示例 1：

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

答案代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        // HashMap 的 key 为排序后的字母组合，value 为原字符串列表
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            // 将字符串转为字符数组并排序，确保异位词得到相同 key
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);

            // 获取已有列表，若无则新建空列表
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }

        ans.addAll(map.values());
        return ans;
    }
}

128. 最长连续序列

题目描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请设计并实现时间复杂度为 O(n) 的算法解决此问题。

答案代码

class Solution {
    public int longestConsecutive(int[] nums) {
        // 1. 将所有数字加入 Set，实现去重并便于 O(1) 查找
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int maxLen = 0; // 记录最长连续序列长度

        // 2. 遍历 Set 中的每个数字
        for (int num : set) {
            // 只从序列起点开始计算（保证 num - 1 不存在）
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentLen = 1;

                // 向后找连续数字
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentLen++;
                }

                // 更新最长长度
                maxLen = Math.max(maxLen, currentLen);
            }
        }

        return maxLen;
    }
}

我的理解

• 哈希的核心价值通常在于把查询复杂度压到 O(1)。
• 在题解里，最常见的两类思路是“值到下标的映射”和“去重 + 快速存在性判断”。

关联笔记

• Hot100首页