哈希表经典算法题整理

2. 力扣 3 - 无重复字符的最长子串

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。 说明：s 由英文字母、数字、符号和空格组成。

带注释代码

import java.util.Arrays;

/**
 * 力扣 3 - 无重复字符的最长子串
 */
public class E02Leetcode3 {
    public int lengthOfLongestSubstring(String s) {
        // 用数组模拟哈希表（ASCII 码范围 0-127），存储字符最后一次出现的下标，初始值 -1 表示未出现
        int[] charIndexMap = new int[128];
        Arrays.fill(charIndexMap, -1);
        int left = 0; // 滑动窗口左边界（无重复子串的起始位置）
        int maxLen = 0; // 记录最长无重复子串长度
        // 滑动窗口右边界遍历字符串
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right); // 当前字符
            int lastIndex = charIndexMap[currentChar]; // 当前字符最后一次出现的下标
            // 若字符已出现过，且最后一次出现位置在窗口内 → 调整左边界到「最后一次出现位置 +1」
            if (lastIndex != -1) {
                left = Math.max(left, lastIndex + 1);
            }
            // 更新当前字符的最后出现位置为当前右边界
            charIndexMap[currentChar] = right;
            // 计算当前窗口长度，更新最大长度（窗口长度=右边界 - 左边界 +1）
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        E02Leetcode3 solution = new E02Leetcode3();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); // 输出 3
        System.out.println(solution.lengthOfLongestSubstring("abca")); // 输出 3
    }
}

解题思路

1. 核心思想：滑动窗口 + 数组模拟哈希表，用窗口维护「无重复子串」范围，用哈希表快速判断字符是否重复；
2. 步骤拆解：
   • 用 left 和 right 表示滑动窗口的左右边界，窗口内始终是无重复子串；
   • 数组 charIndexMap 存储每个字符最后一次出现的下标（替代 HashMap，提升效率）；
   • 右边界遍历字符：若字符已在窗口内重复，将左边界移动到「重复字符最后出现位置 +1」；
   • 每次遍历更新字符最后出现位置，并计算当前窗口长度，更新最大值；
3. 复杂度：时间 O(n)（仅遍历一次字符串），空间 O(1)（数组大小固定为 128）；
4. 哈希表作用：O(1) 时间查询字符最后出现位置，避免遍历窗口判断重复。

3. 力扣 49 - 字母异位词分组

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 说明：字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

带注释代码

import java.util.*;

/**
 * 力扣 49 - 字母异位词分组
 */
public class E03Leetcode49 {
    // 自定义哈希 Key：用 26 位数组统计字符出现次数，重写 equals 和 hashCode 保证哈希表正确性
    static class CharCountKey {
        int[] count = new int[26]; // 对应 a-z 的字符计数

        // 构造器：根据字符串生成字符计数数组
        public CharCountKey(String str) {
            for (char ch : str.toCharArray()) {
                count[ch - 'a']++; // 'a'对应下标 0，统计每个字符出现次数
            }
        }

        // 重写 equals：字符计数数组相同则视为相等（字母异位词）
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CharCountKey that = (CharCountKey) o;
            return Arrays.equals(count, that.count);
        }

        // 重写 hashCode：基于字符计数数组生成哈希值
        @Override
        public int hashCode() {
            return Arrays.hashCode(count);
        }
    }

    // 解法 1：自定义 Key（字符计数数组）
    public List<List<String>> groupAnagrams(String[] strs) {
        // 哈希表：key=字符计数特征，value=该特征对应的所有字母异位词
        HashMap<CharCountKey, List<String>> map = new HashMap<>();
        for (String str : strs) {
            CharCountKey key = new CharCountKey(str);
            // 若 Key 不存在则新建 List，存在则获取已有 List（简化判空逻辑）
            List<String> group = map.computeIfAbsent(key, k -> new ArrayList<>());
            group.add(str); // 将当前字符串加入对应分组
        }
        // 将哈希表的值（所有分组）转为 List 返回
        return new ArrayList<>(map.values());
    }

    // 解法 2：排序字符串作为 Key（更简洁）
    public List<List<String>> groupAnagrams1(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars); // 字母异位词排序后字符串相同
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = new E03Leetcode49().groupAnagrams(strs);
        System.out.println(result); // 输出：[[eat, tea, ate], [tan, nat], [bat]]
    }
}

解题思路

1. 核心思想：提取字母异位词的「唯一特征」作为哈希表 Key，将特征相同的字符串归为一组；
2. 特征提取方式：
   • 方式 1（自定义 Key）：用 26 位数组统计每个字符出现次数，数组相同则为字母异位词（需重写 equals/hashCode）；
   • 方式 2（排序 Key）：将字符串字符排序，字母异位词排序后结果相同；
3. 步骤拆解：
   • 遍历字符串数组，为每个字符串生成唯一特征 Key；
   • 用哈希表存储「Key-字符串列表」映射，将同特征字符串加入同一列表；
   • 最终返回哈希表中所有列表；
4. 复杂度：时间 O(nk)（n 为字符串数量，k 为字符串长度），空间 O(nk)；
5. 哈希表作用：按特征分组，快速聚合字母异位词。

4. 力扣 217 - 存在重复元素

题目描述

给你一个整数数组 nums。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素都互不相同，返回 false。

带注释代码

import java.util.HashMap;
import java.util.HashSet;

/**
 * 力扣 217 - 存在重复元素
 */
public class E04Leetcode217 {
    // 解法 1：HashMap 实现
    public boolean containsDuplicate1(int[] nums) {
        // 哈希表：key=数组元素，value=占位符（仅用于判断存在性）
        HashMap<Integer, Object> map = new HashMap<>(nums.length * 2);
        Object placeholder = new Object();
        for (int num : nums) {
            // put 方法返回旧值：非 null 表示元素已存在，直接返回 true
            Object oldValue = map.put(num, placeholder);
            if (oldValue != null) {
                return true;
            }
        }
        return false;
    }

    // 解法 2：HashSet 实现（更简洁）
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            // add 方法返回 false 表示元素已存在，直接返回 true
            if (!set.add(num)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        E04Leetcode217 solution = new E04Leetcode217();
        System.out.println(solution.containsDuplicate(new int[]{1, 2, 3, 1})); // 输出 true
        System.out.println(solution.containsDuplicate(new int[]{1, 2, 3, 4})); // 输出 false
    }
}

解题思路

1. 核心思想：利用哈希表/集合的「元素唯一性」特性，遍历数组时判断元素是否已存在；
2. 步骤拆解：
   • 解法 1（HashMap）：遍历数组，用 put 方法存储元素，若返回旧值则说明元素重复；
   • 解法 2（HashSet）：遍历数组，用 add 方法添加元素，若返回 false 则说明元素重复；
   • 只要发现重复元素，立即返回 true，遍历结束未发现则返回 false；
3. 复杂度：时间 O(n)，空间 O(n)；
4. 哈希表作用：O(1) 时间判断元素是否已出现，替代暴力法的双层循环。

5. 力扣 136 - 只出现一次的数字

题目描述

给你一个 非空 整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 要求：实现线性时间复杂度、不使用额外空间的解法（位运算），也可实现哈希表解法。

带注释代码

import java.util.HashSet;

/**
 * 力扣 136 - 只出现一次的数字
 */
public class E05Leetcode136 {
    // 解法 1：位运算（异或）- 最优解（空间 O(1)）
    public int singleNumber(int[] nums) {
        int result = nums[0]; // 异或特性：相同数字异或=0，0 异或任何数=数本身
        for (int i = 1; i < nums.length; i++) {
            result ^= nums[i];
        }
        return result;
    }

    // 解法 2：HashSet 实现
    public int singleNumber1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            // add 返回 false 表示元素已存在 → 移除该元素；返回 true 表示首次出现 → 保留
            if (!set.add(num)) {
                set.remove(num);
            }
        }
        // 最终集合中仅存唯一出现一次的元素
        return set.toArray(new Integer[0])[0];
    }

    public static void main(String[] args) {
        E05Leetcode136 solution = new E05Leetcode136();
        System.out.println(solution.singleNumber1(new int[]{2, 2, 1})); // 输出 1
        System.out.println(solution.singleNumber(new int[]{4, 1, 2, 1, 2})); // 输出 4
    }
}

解题思路

解法 1（位运算）

1. 核心思想：利用异或运算的特性：
   • 相同数字异或结果为 0（如 2^2=0）；
   • 0 异或任何数字结果为数字本身（如 0^1=1）；
2. 步骤：遍历数组，将所有元素依次异或，最终结果即为唯一出现一次的数字；
3. 复杂度：时间 O(n)，空间 O(1)。

解法 2（HashSet）

1. 核心思想：利用集合的唯一性，「出现两次的元素添加后又移除，仅保留出现一次的元素」；
2. 步骤：
   • 遍历数组，添加元素到集合：add 返回 false（已存在）则移除，返回 true（首次出现）则保留；
   • 最终集合中仅剩唯一元素；
3. 复杂度：时间 O(n)，空间 O(n)；
4. 哈希表作用：记录元素出现次数（通过添加/移除实现「出现偶数次则删除」）。

6. 力扣 242 - 有效的字母异位词

题目描述

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。 说明：假设字符串只包含小写字母。

带注释代码

import java.util.Arrays;

/**
 * 力扣 242 - 有效的字母异位词
 */
public class E06Leetcode242 {
    public boolean isAnagram(String s, String t) {
        // 若长度不同，直接不是字母异位词
        if (s.length() != t.length()) {
            return false;
        }
        // 分别生成两个字符串的字符计数数组，比较是否相同
        return Arrays.equals(getCharCount(s), getCharCount(t));
    }

    // 生成字符计数数组：统计每个小写字母出现次数
    private int[] getCharCount(String str) {
        int[] countArray = new int[26]; // 对应 a-z
        for (char ch : str.toCharArray()) {
            countArray[ch - 'a']++; // 'a'对应下标 0，统计次数
        }
        return countArray;
    }

    public static void main(String[] args) {
        E06Leetcode242 solution = new E06Leetcode242();
        System.out.println(solution.isAnagram("anagram", "nagaram")); // 输出 true
        System.out.println(solution.isAnagram("rat", "car")); // 输出 false
    }
}

解题思路

1. 核心思想：字母异位词的核心特征是「每个字符出现次数完全相同」，用数组模拟哈希表统计次数；
2. 步骤拆解：
   • 先判断两个字符串长度是否相同：不同则直接返回 false；
   • 分别生成两个字符串的字符计数数组（26 位，对应 a-z）；
   • 比较两个数组是否相同：相同则为字母异位词；
3. 复杂度：时间 O(n)（n 为字符串长度），空间 O(1)（数组大小固定为 26）；
4. 哈希表作用：统计字符出现次数，快速对比两个字符串的字符分布。

7. 力扣 387 - 字符串中的第一个唯一字符

题目描述

给定一个字符串 s，找到 它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 说明：s 只包含小写英文字母。

带注释代码

/**
 * 力扣 387 - 字符串中的第一个唯一字符
 */
public class E07Leetcode387 {
    public int firstUniqChar(String s) {
        // 数组模拟哈希表：统计每个小写字母出现的次数
        int[] charCount = new int[26];
        char[] chars = s.toCharArray();
        // 第一次遍历：统计所有字符出现次数
        for (char ch : chars) {
            charCount[ch - 'a']++;
        }
        // 第二次遍历：找到第一个出现次数为 1 的字符，返回其下标
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            if (charCount[ch - 'a'] == 1) {
                return i;
            }
        }
        // 无唯一字符，返回 -1
        return -1;
    }

    public static void main(String[] args) {
        E07Leetcode387 solution = new E07Leetcode387();
        System.out.println(solution.firstUniqChar("leetcode")); // 输出 0
        System.out.println(solution.firstUniqChar("loveleetcode")); // 输出 2
        System.out.println(solution.firstUniqChar("aabb")); // 输出 -1
    }
}

解题思路

1. 核心思想：两次遍历 + 数组模拟哈希表，第一次统计次数，第二次找首个次数为 1 的字符；
2. 步骤拆解：
   • 第一次遍历：用 26 位数组统计每个字符的出现次数；
   • 第二次遍历：按字符串顺序检查字符次数，第一个次数为 1 的字符即为答案；
3. 复杂度：时间 O(n)（两次遍历字符串），空间 O(1)；
4. 哈希表作用：快速统计字符出现次数，避免逐个字符对比的暴力法。

8. 力扣 819 - 最常见的单词

题目描述

给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多的、不在禁用列表中的单词。 说明：

• 题目保证至少有一个词不在禁用列表中，且答案唯一；
• 段落中的单词不区分大小写，答案返回小写形式。

带注释代码

import java.util.*;

/**
 * 力扣 819 - 最常见的单词
 */
public class E08Leetcode819 {
    // 最优解法：字符遍历（避免 split 的性能损耗）
    public String mostCommonWord(String paragraph, String[] banned) {
        // 禁用词集合：O(1) 时间判断是否为禁用词
        Set<String> bannedSet = Set.of(banned);
        // 哈希表：key=单词，value=出现次数
        HashMap<String, Integer> wordCount = new HashMap<>();
        char[] chars = paragraph.toLowerCase().toCharArray();
        StringBuilder sb = new StringBuilder(); // 拼接当前单词
        // 遍历字符，提取单词并统计次数
        for (char ch : chars) {
            // 是小写字母则拼接，否则处理当前单词
            if (ch >= 'a' && ch <= 'z') {
                sb.append(ch);
            } else {
                String word = sb.toString();
                // 非禁用词且单词非空，统计次数
                if (!bannedSet.contains(word) && !word.isEmpty()) {
                    wordCount.compute(word, (k, v) -> v == null ? 1 : v + 1);
                }
                sb.setLength(0); // 清空字符串构建器
            }
        }
        // 处理最后一个单词（段落末尾无分隔符的情况）
        if (sb.length() > 0) {
            String word = sb.toString();
            if (!bannedSet.contains(word)) {
                wordCount.compute(word, (k, v) -> v == null ? 1 : v + 1);
            }
        }
        // 遍历哈希表，找到出现次数最多的单词
        int maxCount = 0;
        String result = null;
        for (Map.Entry<String, Integer> entry : wordCount.entrySet()) {
            int count = entry.getValue();
            if (count > maxCount) {
                maxCount = count;
                result = entry.getKey();
            }
        }
        return result;
    }

    public static void main(String[] args) {
        E08Leetcode819 solution = new E08Leetcode819();
        String paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
        String[] banned = {"hit"};
        System.out.println(solution.mostCommonWord(paragraph, banned)); // 输出 ball
    }
}

解题思路

1. 核心思想：字符遍历提取单词 + 哈希表统计次数 + 禁用词集合快速过滤；
2. 步骤拆解：
   • 将段落转为小写，遍历字符拼接单词（避免 split 正则的性能损耗）；
   • 用 HashSet 存储禁用词，O(1) 时间判断单词是否禁用；
   • 用 HashMap 统计非禁用词的出现次数；
   • 遍历哈希表，找到次数最多的单词；
3. 复杂度：时间 O(n)（n 为段落长度），空间 O(m)（m 为非禁用词数量）；
4. 哈希表作用：
   • HashSet：快速过滤禁用词；
   • HashMap：统计单词出现次数，快速查找次数最大值。

总结

哈希表在这些题目中的核心应用场景

1. 快速查找/判重：两数之和、存在重复元素（O(1) 时间判断元素是否存在）；
2. 统计计数：字母异位词、第一个唯一字符、最常见单词（统计字符/单词出现次数）；
3. 分组聚合：字母异位词分组（按特征聚合同类元素）；
4. 记录位置/状态：无重复最长子串（记录字符最后出现位置）；
5. 替代暴力循环：所有题目均通过哈希表将暴力法的 O(n²) 时间复杂度优化为 O(n)。

哈希表实现技巧

1. 数组模拟哈希表：针对小写字母（26 位）、ASCII 字符（128 位），效率高于 HashMap；
2. HashSet 简化判重：无需存储值时，用 HashSet 替代 HashMap；
3. computeIfAbsent 简化逻辑：避免手动判空 + 新建集合/赋值；
4. 自定义 Key：需重写 equals 和 hashCode，保证哈希表正确性。