跳到主要内容

哈希表

哈希表利用映射关系实现 O(1) 的平均查找时间。常用场景包括频次统计、值存在性校验、反向映射等。

383. 赎金信 (Ransom Note)​

题目描述​

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路​

频次数组统计。

  1. 使用长度为 26 的整数数组 counts。
  2. 遍历 magazine，将每个字符的计数加 1。
  3. 遍历 ransomNote，将对应字符的计数减 1。
  4. 如果中途某个计数值小于 0，说明 magazine 不足以支撑该子串。

Java 代码实现​

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) return false;
        int[] counts = new int[26];
        for (char c : magazine.toCharArray()) counts[c - 'a']++;
        for (char c : ransomNote.toCharArray()) {
            if (--counts[c - 'a'] < 0) return false;
        }
        return true;
    }
}

205. 同构字符串 (Isomorphic Strings)​

题目描述​

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种替换规则得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射到自己本身。

解题思路​

双向映射校验。

  1. 建立两个 Map 记录映射关系。
  2. 遍历 s 和 t，如果 s[i] 已经映射过且结果不为 t[i]，返回 false。
  3. 如果 t[i] 已经映射过（由 t 映射到 s）且结果不为 s[i]，返回 false。

Java 代码实现​

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<>(), t2s = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            if ((s2t.containsKey(a) && s2t.get(a) != b) || (t2s.containsKey(b) && t2s.get(b) != a)) return false;
            s2t.put(a, b); t2s.put(b, a);
        }
        return true;
    }
}

290. 单词规律 (Word Pattern)​

题目描述​

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向建立的映射关系。

解题思路​

Map + Set 反向检查。

  1. 将 s 按空格拆分为字符串数组。
  2. 建立 char 到 String 的 Map。
  3. 将 pattern 的字符与单词一一对应放入 Map 前查重，确保每一个字符对应唯一一个单词。

Java 代码实现​

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (pattern.length() != words.length) return false;
        Map<Character, String> map = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (map.containsKey(c)) {
                if (!map.get(c).equals(words[i])) return false;
            } else {
                if (map.containsValue(words[i])) return false;
                map.put(c, words[i]);
            }
        }
        return true;
    }
}

242. 有效的字母异位词 (Valid Anagram)​

题目描述​

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意： 若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

解题思路​

数组计频法。由 26 个字母组成的字符串可以用长度 26 的数组作为哈希表实现 O(N) 的时间及 O(1) 的空间。

Java 代码实现​

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
            counts[t.charAt(i) - 'a']--;
        }
        for (int n : counts) if (n != 0) return false;
        return true;
    }
}

49. 字母异位词分组 (Group Anagrams)​

题目描述​

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

字母异位词 是由重新排列源字符串的字母得到的一个新字符串，通常使用每个原始字母恰好一次。

解题思路​

排序作为 Key。 将每个字符串转换成字符数组并排序，排序后的字符串作为 HashMap 的 key，原字符串放入 List。

Java 代码实现​

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

1. 两数之和 (Two Sum)​

题目描述​

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

解题思路​

一次遍历哈希查找。

  1. 在遍历数组时，先查找哈希表中是否存在 target - nums[i]。
  2. 如果存在，直接返回索引。
  3. 如果不存在，将 nums[i] 及其索引存入哈希表。

Java 代码实现​

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<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 null;
    }
}

202. 快乐数 (Happy Number)​

题目描述​

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

解题思路​

记录路径（去重） 或 快慢指针（找环）。 每次将位数平方之和放入 HashSet，如果产生的数字已存在，说明进入了死循环，不再是快乐数。

Java 代码实现​

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) {
            set.add(n);
            int sum = 0;
            while (n > 0) {
                int d = n % 10;
                sum += d * d;
                n /= 10;
            }
            n = sum;
        }
        return n == 1;
    }
}

219. 存在重复元素 II (Contains Duplicate II)​

题目描述​

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

解题思路​

哈希表位置更新。 维护 Map<Integer, Integer> 记录数值到最新下标的映射。如果当前数值已在 Map 中且新旧下标之差不大于 k，则返回 true。

Java 代码实现​

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) return true;
            map.put(nums[i], i);
        }
        return false;
    }
}

128. 最长连续序列 (Longest Consecutive Sequence)​

题目描述​

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

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

解题思路​

HashSet 统计起点。

  1. 将所有数放入 HashSet 去重且提高查询效率。
  2. 遍历集合中的数 num。只有当 num - 1 不存在在集合中时，才把其作为起点开始计数。
  3. 反复尝试 num + 1 统计并更新 maxLen。

Java 代码实现​

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int maxLen = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) {
                int curr = n, len = 1;
                while (set.contains(++curr)) len++;
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}