LeetCode 热题100 哈希

LeetCode 热题100 中哈希的题目分析和总结

什么是哈希，如何理解算法程序设计中的哈希

哈希（Hash），又称散列，是一种将任意长度的输入（键，Key）通过散列算法（哈希函数）变换成固定长度的输出（哈希值/索引）的映射过程。

在算法程序设计中，我们通常通过 哈希表（Hash Table） 来应用哈希思想。理解哈希，可以抓住以下几个核心概念：

核心目的（空间换时间）： 哈希表的最主要目的是实现快速查找。在数组或链表中查找一个元素通常需要遍历，时间复杂度为 $O(n)$ 。而通过哈希表，我们可以根据键值直接计算出存储位置，从而将平均查找、插入和删除的时间复杂度降低到 $O(1)$ 。
键值对（Key-Value Pair）： 哈希表通常存储的是键值对。你可以把哈希表想象成一本字典，Key 是你要查的单词，Value 是单词的释义。只要知道单词（Key），就能瞬间翻到对应的那一页找到释义（Value）。
哈希冲突（Hash Collision）： 因为输出的哈希值空间通常小于输入的键空间，不同的键可能会被映射到同一个位置，这就是哈希冲突。常见的解决办法有“拉链法”（在该位置挂一个链表）和“开放寻址法”。
各语言中的实现：

Java: HashMap, HashSet
Python: 字典 dict, 集合 set
C++: unordered_map, unordered_set
JavaScript: Map, Set, 或直接使用对象 {}

总结： 当你在算法题中遇到需要 频繁查找某个元素是否存在 或者 建立两种数据之间的映射关系 时，第一时间就应该想到使用哈希表。

题目一：两数之和

问题介绍

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

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

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

基础示例

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

$2 \le \text{nums.length} \le 10^4$
$-10^9 \le \text{nums[i]} \le 10^9$
$-10^9 \le \text{target} \le 10^9$
只会存在一个有效答案

问题分析

这道题是经典的“查找需求”问题。对于数组中的每一个元素 nums[i]，我们实际上是在寻找数组中是否还存在另一个元素，其值为 target - nums[i]。

思路一：暴力枚举（不推荐）

最直观的想法是使用两层嵌套循环。外层循环遍历数组中的每一个元素 x，内层循环寻找数组中是否存在 target - x。

时间复杂度： $O(n^2)$ ，因为对于每个元素都需要遍历其余元素。当数据量大时会超时。
空间复杂度： $O(1)$ 。

思路二：哈希表法（最优解）

为了将寻找 target - nums[i] 的时间复杂度从 $O(n)$ 降低到 $O(1)$ ，我们可以使用哈希表。

创建一个空的哈希表，用于存储已经遍历过的元素及其对应的下标。其中，哈希表的 Key 为数组元素的值，Value 为该元素的下标。
遍历数组 nums：
- 当前遍历到元素 num = nums[i]。
- 计算我们需要寻找的配对目标值：complement = target - num。
- 检查哈希表： 看看 complement 是否已经存在于哈希表中？
- 如果存在： 说明我们找到了匹配的两个数。哈希表中存的下标就是第一个数的下标，当前的索引 i 就是第二个数的下标。直接返回即可。
- 如果不存在： 说明当前元素 num 的另一半还没出现（或者当前元素就是后面某个元素的另一半）。我们将当前的 num 和它的索引 i 存入哈希表中：hash_table[num] = i，然后继续遍历下一个元素。

这种方法巧妙地利用了哈希表“边遍历、边存储、边查找”的特性，确保每个元素只被访问一次，有效避免了重复寻找。

时间复杂度： $O(n)$ ，其中 $n$ 是数组中的元素数量。对于每一个元素，我们只需要 $O(1)$ 的时间去哈希表中进行查找和插入。
空间复杂度： $O(n)$ ，其中 $n$ 是数组中的元素数量。哈希表最多需要存储 $n$ 个键值对。

Python 代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 创建一个字典作为哈希表，存储 {元素值: 元素索引}
        hash_map = {}

        for i, num in enumerate(nums):
            # 计算当前元素需要的配对值
            complement = target - num

            # 如果配对值已经在哈希表中，说明找到了答案
            if complement in hash_map:
                return [hash_map[complement], i]

            # 如果没找到，将当前元素及其索引存入哈希表，供后续元素查找
            hash_map[num] = i

        return [] # 根据题意，必定有解，这里只是为了代码完整性

思路三：排序 + 双指针法（进阶思想）

虽然哈希表是本题的最优解，但“排序 + 双指针”是处理数组求和问题（如“三数之和”）时非常经典且通用的一种思想，非常值得掌握。

需要注意的是，本题要求返回的是元素的原始下标。如果直接对原数组进行排序，元素的原始下标就会被打乱丢失。因此，我们在排序前需要先将元素的值和它对应的原始下标“绑定”在一起。

记录原始下标： 创建一个新的数组（或列表），存储 (元素值, 原始下标) 的组合。
按值排序： 对这个新数组按照“元素值”从小到大进行排序。
双指针向中间逼近：
- 初始化两个指针：左指针 left 指向数组起始位置 0，右指针 right 指向数组末尾位置 n - 1。
- 计算当前左右指针对应元素值的和：current_sum = sorted_nums[left].value + sorted_nums[right].value。
- 如果 current_sum == target： 找到了目标组合，提取它们绑定的原始下标并返回即可。
- 如果 current_sum < target： 说明当前和偏小。因为数组已经有序，我们需要将左指针向右移动一位（left += 1），用更大的数来尝试，使得和增大。
- 如果 current_sum > target： 说明当前和偏大。我们需要将右指针向左移动一位（right -= 1），用更小的数来尝试，使得和减小。
- 重复上述过程，直到 left 和 right 相遇。

时间复杂度： $O(n \log n)$ 。排序的时间复杂度为 $O(n \log n)$ ，双指针遍历数组的时间复杂度为 $O(n)$ ，综合起来为 $O(n \log n)$ 。
空间复杂度： $O(n)$ 。我们需要额外的空间来存储包含元素及其原始下标的元组列表。

Python 代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 1. 将元素值和原始索引组合在一起，形成 (num, index) 的列表
        nums_with_index = [(num, i) for i, num in enumerate(nums)]

        # 2. 按照元素值从小到大进行排序
        nums_with_index.sort(key=lambda x: x[0])

        # 3. 初始化左右双指针
        left, right = 0, len(nums) - 1

        while left < right:
            current_sum = nums_with_index[left][0] + nums_with_index[right][0]

            if current_sum == target:
                # 找到目标值，返回原始索引
                return [nums_with_index[left][1], nums_with_index[right][1]]
            elif current_sum < target:
                # 和太小，左指针右移以增大和
                left += 1
            else:
                # 和太大，右指针左移以减小和
                right -= 1

        return []

题目二：字母异位词分组

问题介绍

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

补充说明： 字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。简单来说，就是包含的字母种类和数量完全相同，只是顺序不同的字符串。

基础示例

示例 1：

输入： strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出： [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
解释： strs 中没有字符串可以通过重新排列来形成 "bat"。字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。字符串 "ate"，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2：

输入： strs = [""]
输出： [[""]]

示例 3：

输入： strs = ["a"]
输出： [["a"]]

提示：

$1 \le \text{strs.length} \le 10^4$
$0 \le \text{strs[i].length} \le 100$
strs[i] 仅包含小写英文字母

问题分析

处理字母异位词的核心在于寻找一种统一的特征，使得互为字母异位词的字符串拥有相同的特征。有了这个特征，我们就可以用哈希表将特征相同的字符串分到同一组。

思路一：排序 + 哈希表

互为字母异位词的两个字符串包含的字母相同。因此，如果对这两个字符串分别进行排序，排序后的字符串一定是相同的。我们可以将排序后的字符串作为哈希表的键（Key），将原始字符串组成的列表作为哈希表的值（Value）。

时间复杂度： $O(n k \log k)$ ，其中 $n$ 是字符串数组的数量， $k$ 是字符串的最大长度。遍历数组需要 $O(n)$ ，对每个字符串排序需要 $O(k \log k)$ 。
空间复杂度： $O(nk)$ ，哈希表需要存储所有的字符串。

Python 代码实现

import collections

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        # 创建一个默认值为列表的字典作为哈希表
        hash_map = collections.defaultdict(list)

        for s in strs:
            # 将字符串按字母顺序排序，并拼接回字符串作为键
            sorted_s = "".join(sorted(s))
            # 将原始字符串加入到对应特征键的列表中
            hash_map[sorted_s].append(s)

        # 返回哈希表中所有的值组成的列表
        return list(hash_map.values())

思路二：计数 + 哈希表（进阶优化）

由于题目说明字符串只包含小写字母，互为字母异位词的两个字符串中字符出现的频次一定相同。我们可以通过统计每个字符串中 26 个字母的出现次数，并将这个频次数组转换为不可变的元组（Tuple）作为哈希表的键。这种方法省去了排序的时间开销。

时间复杂度： $O(n \times k)$ ，其中 $n$ 是字符串数组的数量， $k$ 是字符串的最大长度。我们需要遍历每个字符串并统计字符频次。
空间复杂度： $O(n \times k)$ ，哈希表需要存储所有的字符串，并且包含长度为 26 的频次元组。

Python 代码实现

import collections

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        # 创建一个默认值为列表的字典作为哈希表
        hash_map = collections.defaultdict(list)

        for s in strs:
            # 创建一个长度为 26 的数组统计字符频次
            counts = [0] * 26
            for char in s:
                # 利用 ASCII 码计算字符对应的索引位置
                counts[ord(char) - ord('a')] += 1

            # 列表不可哈希，必须转换为元组作为哈希表的键
            hash_map[tuple(counts)].append(s)

        # 返回哈希表中所有的值组成的列表
        return list(hash_map.values())

题目三：最长连续序列

问题介绍

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

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

基础示例

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

输入：nums = [1,0,1,2]
输出：3

提示：

$0 \le \text{nums.length} \le 10^5$
$-10^9 \le \text{nums[i]} \le 10^9$

问题分析

这道题的核心难点在于题目明确要求了 $O(n)$ 的时间复杂度。这意味着我们不能使用常规的排序方法。

思路：哈希集合法

为了在 $O(n)$ 的时间复杂度内完成查找，我们可以利用哈希表（具体来说是哈希集合 HashSet）能在 $O(1)$ 时间内完成元素查找的特性。

去重与存储： 首先，我们将数组中的所有元素放入一个哈希集合中。这不仅可以去除重复元素（重复元素对计算最长连续序列没有帮助，如示例 3），还能让我们后续以 $O(1)$ 的时间复杂度判断某个数是否存在。
寻找序列起点： 遍历哈希集合中的每一个元素 num。我们如何避免重复计算同一个序列呢？关键在于：只从每个连续序列的“起点”开始向后匹配。
- 如果集合中存在 num - 1，说明当前的 num 只是某个序列的中间部分，我们直接跳过，不作处理。
- 如果集合中不存在 num - 1，说明当前的 num 必定是一个连续序列的起点。
计算序列长度： 一旦确认 num 是一个起点，我们就通过一个 while 循环，不断查找 num + 1、num + 2… 是否存在于集合中，并记录当前连续序列的长度。
更新最大长度： 将当前序列的长度与全局保存的最大长度进行比较，保留较大者。

这种方法巧妙地利用了“寻找起点”的策略，确保了集合中的每个数字实际上只被内部的 while 循环访问一次（或者零次），从而保证了整体线性的时间复杂度。

时间复杂度： $O(n)$ ，其中 $n$ 是数组的长度。虽然代码中有一个嵌套的 while 循环，但因为我们只有在遇到序列起点时才会进入内层循环，所以数组中的每个数最多只会被访问两次（一次是在外层 for 循环，一次是在内层 while 循环）。整体时间复杂度依然是线性的。
空间复杂度： $O(n)$ ，哈希集合最多需要存储 $n$ 个不重复的元素。

Python 代码实现

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 如果数组为空，直接返回 0
        if not nums:
            return 0

        # 将数组转换为集合，实现去重和 O(1) 的查找
        num_set = set(nums)
        longest_streak = 0

        # 遍历集合中的每一个数字
        for num in num_set:
            # 判断当前数字是否是一个连续序列的起点
            # 如果 num - 1 不在集合中，说明它是起点
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                # 不断向后查找连续的数字
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                # 更新最长连续序列的长度
                longest_streak = max(longest_streak, current_streak)

        return longest_streak

题目四：无重复字符的最长子串

问题介绍

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

注意： “子串”指的是字符串中连续的一段字符序列，而“子序列”可以是不连续的。例如，在字符串 "pwwkew" 中，"wke" 是子串，而 "pwke" 是子序列。

基础示例

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

提示：

$0 \le \text{s.length} \le 5 \times 10^4$
s 由英文字母、数字、符号和空格组成。

问题分析

这道题的核心在于寻找一段“连续且不重复”的字符区间。由于要求的是“最长”的区间长度，当我们在遍历字符串时，需要一种机制来动态地调整我们当前正在考察的子串范围。

思路一：暴力枚举（不推荐）

最直接的想法是枚举出所有的子串，然后逐一检查这些子串中是否有重复字符。如果有，则跳过；如果没有，则更新最长子串的长度记录。

时间复杂度： $O(n^3)$ 。枚举所有子串需要 $O(n^2)$ 的时间，而对于每个子串，检查是否有重复字符还需要 $O(n)$ 的时间。在字符串较长时，这种方法会严重超时。
空间复杂度： $O(\min(m, n))$ ，其中 $m$ 是字符集的大小。我们需要额外的空间来验证子串中是否有重复字符。

思路二：滑动窗口 + 哈希集合（基础解法）

为了避免重复计算，我们可以使用“滑动窗口”的思想。窗口可以看作是字符串上的一段“视野”，我们用左右两个指针 left 和 right 来划定这个窗口的边界。

我们使用一个哈希集合（Set）来记录当前窗口内出现过的字符。
初始时，left 和 right 都停留在字符串的起始位置，窗口大小为 0。
扩大窗口： 尝试将 right 指针向右移动，把新字符加入窗口。
- 如果新字符不在哈希集合中：说明当前窗口内没有重复字符。我们将该字符加入集合，更新最长子串的长度，并将 right 指针继续向右移动。
- 如果新字符已经存在于哈希集合中：说明出现了重复字符。此时，我们需要缩小窗口。将 left 指针不断向右移动，并将移出窗口的字符从哈希集合中删除，直到集合中不再包含那个导致重复的新字符为止。
重复步骤 3，直到 right 指针遍历完整个字符串。

时间复杂度： $O(n)$ ，其中 $n$ 是字符串的长度。虽然有两个指针，但每个字符最多被 right 指针访问一次，被 left 指针访问一次，总操作次数为 $2n$ 。
空间复杂度： $O(|\Sigma|)$ ，其中 $\Sigma$ 表示字符集（即字符串中可能出现的字符种类数）。哈希集合中最多存储 $|\Sigma|$ 个不同的字符。

Python 代码实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_length = 0

        for right in range(len(s)):
            # 如果右指针指向的字符已经在集合中，说明有重复
            # 我们需要不断向右移动左指针，直到移出那个重复的字符
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1

            # 将当前字符加入集合
            char_set.add(s[right])
            # 更新最长无重复子串的长度
            max_length = max(max_length, right - left + 1)

        return max_length

思路三：滑动窗口 + 哈希映射（优化解法）

在思路二中，当发现重复字符时，left 指针是一步一步向右移动的。其实我们可以利用哈希字典（Map）来进一步优化：直接记录每个字符最后一次出现的索引。

使用一个字典 char_index_map，存储 {字符: 字符最后出现的下标}。
遍历字符串，right 指针向右移动。
如果当前字符 s[right] 已经在字典中，并且它上次出现的下标大于或等于当前的 left 指针：

说明这个重复字符就包含在当前的窗口内。
我们不需要让 left 一步步走，而是直接让 left 跳跃到该重复字符上次出现位置的下一个位置（即 char_index_map[s[right]] + 1），从而一步到位地把重复字符踢出新窗口。

将当前字符及其下标更新到字典中。
更新最大长度。

这种方法是对滑动窗口的常数级优化，代码也更为简洁。

时间复杂度： $O(n)$ 。right 指针遍历一次字符串，left 指针直接跳跃，每个字符只会被访问一次。
空间复杂度： $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集的大小。字典中最多存储 $|\Sigma|$ 个键值对。

Python 代码实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 创建字典记录字符最后一次出现的索引：{char: index}
        char_index_map = {}
        left = 0
        max_length = 0

        for right, char in enumerate(s):
            # 如果字符已经出现过，并且它上次出现的位置在当前窗口内
            if char in char_index_map and char_index_map[char] >= left:
                # 直接将 left 指针跳到该重复字符上次出现位置的下一个位置
                left = char_index_map[char] + 1

            # 更新/插入当前字符的最新索引
            char_index_map[char] = right

            # 计算当前窗口长度并更新最大值
            max_length = max(max_length, right - left + 1)

        return max_length

题目五：字符串所有字母异位词

问题介绍

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括原字符串）。换句话说，如果两个字符串的长度相同，且每个字符出现的次数也都相同，那么它们就是互为异位词。

基础示例

示例 1：

输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：
- 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
- 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2：

输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：
- 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
- 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
- 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示：

$1 \le \text{s.length}, \text{p.length} \le 3 \times 10^4$
s 和 p 仅包含小写字母

问题分析

这道题的核心在于：如何在母串 s 中快速匹配子串 p 的字符构成。因为异位词只关注“字符的种类和数量”而不关注“字符的顺序”，所以我们很容易想到哈希表或数组计数。又因为我们需要在 s 中匹配一个固定长度（即 p 的长度）的子串，这非常符合滑动窗口的应用场景。

思路一：暴力枚举（不推荐）

最直接的方法是遍历字符串 s 中每一个长度等于 p.length 的子串，然后统计这个子串的字符频率，并与 p 的字符频率进行对比。

时间复杂度： $O((n - m + 1) \times m)$ ，其中 $n$ 是字符串 s 的长度， $m$ 是字符串 p 的长度。每次截取子串并统计频率都需要遍历 $m$ 个字符，当字符串很长时会引发超时。
空间复杂度： $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集。这里全是小写字母，空间复杂度约为 $O(26) = O(1)$ 。

思路二：滑动窗口 + 数组计数（最优解）

既然子串的长度是固定的（长度为 len(p)），我们可以在字符串 s 上维护一个长度为 len(p) 的滑动窗口。

题目限定了仅包含小写字母，我们可以用两个长度为 26 的数组来代替哈希表，分别记录 p 的字符频率和当前滑动窗口内的字符频率。

初始化： 如果 s 的长度小于 p，直接返回空列表。先统计 p 中各字符的频率，并统计 s 中前 len(p) 个字符的频率，存入两个数组中。
比较第一个窗口： 比较这两个数组，如果完全相同，说明起始索引 0 是一个有效答案。
滑动窗口： 从索引 len(p) 开始遍历 s，每次将窗口向右滑动一位：
- 将移出窗口的字符在数组中的计数减 1（左边界字符）。
- 将新进入窗口的字符在数组中的计数加 1（右边界字符）。
- 比较两个数组是否相同，如果相同，记录当前的起始索引。

这种方法避免了每次都重新统计子串的所有字符，每次窗口滑动只需要更新两个字符的计数。

时间复杂度： $O(n + m + |\Sigma|)$ ，其中 $n$ 和 $m$ 分别是 s 和 p 的长度， $\Sigma$ 是字符集大小（此处为 26）。滑动窗口在 s 上滑动的时间复杂度是 $O(n)$ ，每次比较数组需要 $O(26)$ 的时间。总体上可以看作线性的 $O(n)$ 。
空间复杂度： $O(|\Sigma|) = O(1)$ 。我们只使用了固定长度（26）的数组来存储字符频率，因此空间消耗为常数级别。

Python 代码实现

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        res = []

        # 如果 s 的长度小于 p 的长度，不可能存在异位词
        if s_len < p_len:
            return res

        # 使用长度为 26 的数组记录小写字母出现的频率
        p_count = [0] * 26
        window_count = [0] * 26

        # 初始化 p 的频次数组和 s 的第一个窗口的频次数组
        for i in range(p_len):
            p_count[ord(p[i]) - ord('a')] += 1
            window_count[ord(s[i]) - ord('a')] += 1

        # 检查第一个窗口是否为异位词
        if p_count == window_count:
            res.append(0)

        # 开始滑动窗口
        for i in range(p_len, s_len):
            # 新字符进入窗口（右侧加入）
            window_count[ord(s[i]) - ord('a')] += 1
            # 旧字符离开窗口（左侧移出）
            # 当前窗口的起始索引为 i - p_len + 1，离开的字符索引为 i - p_len
            window_count[ord(s[i - p_len]) - ord('a')] -= 1

            # 判断当前窗口是否匹配
            if p_count == window_count:
                res.append(i - p_len + 1)

        return res

思路三：滑动窗口 + 差异变量优化（进阶思想）

在思路二中，我们每次窗口滑动后，都需要花费 $O(26)$ 的时间去比较两个数组是否完全相同。虽然常数时间很快，但我们可以通过维护一个“差异值（diff）”来进行进一步的极致优化。

我们只用一个大小为 26 的数组 count 来记录滑动窗口和字符串 p 的字符频率差异（窗口中的字符频次减去 p 中的字符频次）。
我们引入一个变量 diff，记录 count 数组中值不为 0 的元素个数（即频率不匹配的字母种类数）。
窗口滑动时，我们只更新发生变化的字符。如果某个字符的差异值从非 0 变成了 0，说明这个字母匹配上了，diff -= 1；如果从 0 变成了非 0，说明这个字母变得不匹配了，diff += 1。
当 diff == 0 时，说明所有字母的频率都完全一致，记录当前窗口起始索引。

时间复杂度： $O(n + m)$ 。去掉了每次比较数组的常数项消耗，运行效率会更高。
空间复杂度： $O(|\Sigma|) = O(1)$ 。

Python 代码实现

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        if s_len < p_len:
            return []

        res = []
        count = [0] * 26

        # 初始化差异数组
        for i in range(p_len):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(p[i]) - ord('a')] -= 1

        # 统计差异值为非 0 的字符种类数
        diff = sum(1 for c in count if c != 0)

        if diff == 0:
            res.append(0)

        # 窗口滑动
        for i in range(p_len, s_len):
            # x 是新进入窗口的字符，y 是离开窗口的字符
            x, y = ord(s[i]) - ord('a'), ord(s[i - p_len]) - ord('a')

            if x == y:
                # 进出字符相同，对差异没有影响，直接判断即可
                if diff == 0:
                    res.append(i - p_len + 1)
                continue

            # 处理新进入窗口的字符
            if count[x] == 0:  # 原本匹配，现在多了一个，变得不匹配
                diff += 1
            count[x] += 1
            if count[x] == 0:  # 原本少一个，现在补上了，变得匹配
                diff -= 1

            # 处理离开窗口的字符
            if count[y] == 0:  # 原本匹配，现在少了一个，变得不匹配
                diff += 1
            count[y] -= 1
            if count[y] == 0:  # 原本多一个，现在移除了，变得匹配
                diff -= 1

            if diff == 0:
                res.append(i - p_len + 1)

        return res

题目六：和为 K 的子数组

问题介绍

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

子数组是数组中元素的连续非空序列。

基础示例

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
解释：满足条件的子数组为 nums[0..1] 和 nums[1..2]。

示例 2：

输入：nums = [1,2,3], k = 3
输出：2
解释：满足条件的子数组为 nums[0..1] (和为 1+2=3) 和 nums[2..2] (和为 3)。

提示：

$1 \le \text{nums.length} \le 2 \times 10^4$
$-1000 \le \text{nums[i]} \le 1000$
$-10^7 \le k \le 10^7$

问题分析

这道题是经典的“子数组求和”问题。由于题目中明确说明了数组元素可能为负数（ $-1000 \le \text{nums[i]} \le 1000$ ），因此我们不能使用双指针/滑动窗口（因为加入新元素后，子数组的和不一定会单调增加，滑动窗口的收缩条件也就失效了）。

思路一：暴力枚举（不推荐）

最直观的方法是枚举数组中所有的子数组。我们可以固定子数组的左边界 i，然后枚举右边界 j，在每次向右扩展的过程中累加元素的值，并判断和是否等于 k。

时间复杂度： $O(n^2)$ ，其中 $n$ 是数组的长度。我们需要两层循环来枚举所有的子数组。鉴于题目中 $n$ 最大可达 $2 \times 10^4$ ， $n^2$ 的操作量会达到 $4 \times 10^8$ ，在 LeetCode 中很容易引起超时（Time Limit Exceeded）。
空间复杂度： $O(1)$ ，只需要常数级别的额外空间来记录当前的和与符合条件的个数。

思路二：前缀和 + 哈希表优化（最优解）

为了将时间复杂度优化到 $O(n)$ ，我们需要引入前缀和（Prefix Sum）的概念。

前缀和 prefix_sum[i] 表示从数组起始位置到索引 i（包含 i）的所有元素之和。
那么，任意一个子数组 nums[j..i] 的和，就可以表示为两个前缀和的差值：
sum(nums[j..i]) = prefix_sum[i] - prefix_sum[j-1]

题目要求解的是 sum(nums[j..i]) == k。
将其代入上面的等式，得到：prefix_sum[i] - prefix_sum[j-1] == k。
稍作移项转换，就变成了我们在遍历到索引 i 时需要寻找的目标：
prefix_sum[j-1] == prefix_sum[i] - k

这就巧妙地将问题转化为了类似“两数之和”的问题：我们只要在遍历数组计算当前前缀和 prefix_sum[i] 的同时，利用哈希表去查找之前是否出现过值为 prefix_sum[i] - k 的前缀和，出现了几次。

初始化： 创建一个哈希表 prefix_sum_map 来记录各个前缀和出现的次数。极其重要的一步是初始化 prefix_sum_map = {0: 1}。这代表前缀和为 0 的情况出现过 1 次。这是为了处理子数组恰好从索引 0 开始且和为 k 的情况（此时 prefix_sum[i] - k == 0）。
遍历数组： 维护一个变量 prefix_sum 累加当前的元素值。
查找匹配： 计算需要寻找的配对值 target = prefix_sum - k。如果 target 在哈希表中，说明找到了几个符合条件的子数组，将对应出现的次数累加到最终结果 count 中。
更新哈希表： 将当前计算出的 prefix_sum 也存入哈希表中，供后续的元素查找。

时间复杂度： $O(n)$ ，其中 $n$ 是数组的长度。我们只需要遍历数组一次，每次在哈希表中查询和更新数据的平均时间复杂度都是 $O(1)$ 。
空间复杂度： $O(n)$ 。哈希表最多需要存储 $n + 1$ 个不同的前缀和键值对。

Python 代码实现

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0         # 记录和为 k 的子数组个数
        prefix_sum = 0    # 记录当前的前缀和

        # 哈希表记录【前缀和】出现的【次数】
        # 初始化 {0: 1} 是为了覆盖子数组从头开始，且本身和就等于 k 的情况
        prefix_sum_map = {0: 1}

        for num in nums:
            prefix_sum += num  # 计算到当前位置的前缀和

            # 我们要找的历史前缀和等于 prefix_sum - k
            target = prefix_sum - k

            # 如果这个历史前缀和在之前出现过，说明存在和为 k 的连续子数组
            if target in prefix_sum_map:
                count += prefix_sum_map[target]

            # 将当前的前缀和存入哈希表，如果已存在则次数 + 1
            prefix_sum_map[prefix_sum] = prefix_sum_map.get(prefix_sum, 0) + 1

        return count

题目七：最小覆盖子串

问题介绍

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

注意： 测试用例保证答案唯一。

基础示例

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

$m == \text{s.length}$
$n == \text{t.length}$
$1 \le m, n \le 10^5$
s 和 t 由英文字母组成

问题分析

这是一道非常经典且具有代表性的 LeetCode 困难 (Hard) 级别题目。与之前的“找到字符串中所有字母异位词”不同，这道题中我们需要寻找的子串长度是不固定的。因此，我们需要一个可以动态伸缩的滑动窗口。

这道题的核心逻辑可以总结为：“先向右扩张找可行解，再向左收缩找最优解”。

思路一：暴力枚举（不推荐）

最暴力的做法是找出字符串 s 的所有子串，然后逐一检查这些子串是否包含了 t 中的所有字符。

时间复杂度： $O(m^2 \times n)$ 甚至是 $O(m^3)$ ，因为 s 的子串数量是 $O(m^2)$ 级别的，每次检查还需要遍历子串和 t。对于 $10^5$ 的数据量，一定会超时。

思路二：可变滑动窗口 + 哈希表（最优解，满足进阶 $O(m+n)$ 要求）

为了高效解决这个问题，我们维护一个在字符串 s 上滑动的窗口，并使用哈希表（或字典）来记录字符的频率。

准备工作：
- 使用一个哈希表 need 记录字符串 t 中每个字符需要的数量。
- 使用另一个哈希表 window 记录当前滑动窗口中这些字符的出现次数。
- 定义一个变量 valid，表示窗口中已经满足 need 条件的字符种类数（不是字符总数）。例如 t = "aab"，当窗口里有两个 ‘a’ 时，对于 ‘a’ 这个字符的条件才算满足，此时 valid 增加 1。
右指针扩张（寻找可行解）：
- 初始化左右指针 left = 0, right = 0。
- 将 right 指针不断向右移动，把遍历到的字符加入 window。
- 如果加入的字符在 need 中，并且 window 中该字符的数量达到了 need 中的数量要求，我们就将 valid 加 1。
左指针收缩（寻找最优解）：
- 当 valid == len(need) 时，说明当前窗口已经包含了 t 中的所有字符（这是一个可行解）。
- 此时，我们尝试将 left 指针向右移动，以缩小窗口长度。
- 每次移动前，更新并记录当前看到的“最短子串”的起始位置和长度。
- 将移出窗口的字符从 window 中减去。如果该字符是 need 中的字符，且移出后 window 中的数量小于了 need 中的要求，我们就将 valid 减 1。
- valid 减小意味着窗口不再满足条件，我们需要跳出收缩过程，继续移动 right 指针去寻找下一个可行解。

时间复杂度： $O(m + n)$ ，其中 $m$ 是 s 的长度， $n$ 是 t 的长度。虽然代码中有一个嵌套的 while 循环，但左右指针 left 和 right 都只会向右移动，最多各遍历字符串 s 一次。哈希表的操作时间复杂度为 $O(1)$ 。
空间复杂度： $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集。由于题目说明只包含英文字母，哈希表最多存储 52 个键值对（大小写字母），可以认为是 $O(1)$ 的常数级额外空间。

Python 代码实现

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 统计 t 中各字符的频次需求
        from collections import Counter
        need = Counter(t)
        window = {}

        left, right = 0, 0
        valid = 0  # 记录窗口中满足 need 频次要求的字符种类数

        # 记录最小覆盖子串的起始索引及长度
        start = 0
        min_len = float('inf')

        while right < len(s):
            # c 是将移入窗口的字符
            c = s[right]
            right += 1

            # 如果 c 是我们需要寻找的字符，更新窗口数据
            if c in need:
                window[c] = window.get(c, 0) + 1
                # 如果该字符在窗口中的频次达到了 t 中的要求，valid 加 1
                if window[c] == need[c]:
                    valid += 1

            # 当窗口包含了 t 中所有字符时，尝试收缩左边界
            while valid == len(need):
                # 更新最小覆盖子串的记录
                if right - left < min_len:
                    start = left
                    min_len = right - left

                # d 是将移出窗口的字符
                d = s[left]
                left += 1

                # 如果移出的字符是我们需要的字符，更新窗口数据
                if d in need:
                    # 如果移出后，该字符的频次不再满足要求，valid 减 1
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

        # 如果 min_len 没有被更新过，说明没有找到符合条件的子串
        return "" if min_len == float('inf') else s[start:start + min_len]

总结：哈希类题目的通用解题思路

纵观上述 LeetCode 热题 100 中的哈希相关题目，我们可以发现，尽管题目要求和表现形式各异，但它们在底层逻辑和解题套路上有着高度的统一。掌握这些共通之处，能够帮助我们在遇到新问题时迅速建立思路。

核心思想

空间换时间与 $O(1)$ 查找

所有这些题目的共同基础，都是利用哈希表（或哈希集合、数组计数）来牺牲一定的内存空间，换取时间复杂度的大幅降低。

消除嵌套循环：在没有哈希表时，寻找配对元素或检查重复通常需要 $O(n^2)$ 的暴力枚举时间。引入哈希表后，我们可以将历史状态记录下来，使得后续的查找过程降为 $O(1)$ ，从而将整体时间复杂度控制在 $O(n)$ 级别。
边遍历边记录：哈希表不仅用于查找，还用于“动态登记”。在一次遍历的过程中，我们通常是先检查哈希表中是否满足条件，然后再将当前元素或状态更新入哈希表，供后续元素使用。

通用解题套路

针对不同的题型，哈希表的应用可以归纳为以下四种经典套路：

套路一：目标配对法（逆向思维）

适用场景：求和问题、寻找特定差值问题。
代表题目：两数之和、和为 K 的子数组。
核心思路：不要顺着去想“当前元素加上谁等于目标”，而是逆向思考“我当前需要什么配对值”。在“两数之和”中，我们寻找 target - nums[i]；在“和为 K 的子数组”中，我们寻找前缀和 prefix_sum - k。将寻找的过程交给哈希表即可。

套路二：特征归类法

适用场景：分组问题、同构/异位词判断。
代表题目：字母异位词分组。
核心思路：寻找一组数据的统一特征，并将其作为哈希表的 Key。例如，将字符串排序后的结果，或者字符出现频次的不可变元组（Tuple）作为 Key，将具有相同特征的原始数据存入 Value 的列表中。

套路三：哈希集合去重与起点定位

适用场景：连续序列寻找、需要 $O(1)$ 判断元素是否存在的场景。
代表题目：最长连续序列。
核心思路：利用 HashSet 天然的去重和极速查找特性。在此基础上，通过判断 num - 1 是否存在来巧妙地过滤掉非起点元素，确保内层探测逻辑只会从真正的序列起点开始，严格保障线性的时间复杂度。

套路四：滑动窗口的“记账本”

适用场景：子串匹配。
代表题目：无重复字符的最长子串、字符串所有字母异位词、最小覆盖子串。
核心思路：在滑动窗口（双指针）向右扩张和左边界收缩的过程中，哈希表（或定长数组）充当了状态记账本的角色。它记录了当前窗口内各个字符的出现频次或最后出现的位置索引，帮助我们以常数时间判断当前窗口是否合法（如是否包含重复字符、是否覆盖了目标字符串的所有字母），从而指导左右指针的移动。

终极建议：

在进行算法机试或面试时，只要题目中出现 “次数”、“分组”、“配对”、“子串包含/去重” 等字眼，并且对时间复杂度有较高要求（如 $O(n)$ ），请毫不犹豫地在脑海中引入哈希表或计数数组来进行破题。

算法程序设计

#LeetCode热题100

LeetCode 热题100 哈希

https://huan-yin.github.io/2026/03/13/LeetCode热题100哈希/

作者

李相越

发布于

2026年3月13日

许可协议

生成简历编辑网站上一篇

个人博客网站的搭建与部署下一篇

LeetCode 热题100 哈希

LeetCode 热题100 哈希

什么是哈希，如何理解算法程序设计中的哈希

题目一：两数之和

问题介绍

基础示例

问题分析

思路一：暴力枚举（不推荐）

思路二：哈希表法（最优解）

思路三：排序 + 双指针法（进阶思想）

题目二：字母异位词分组

问题介绍

基础示例

问题分析

思路一：排序 + 哈希表

思路二：计数 + 哈希表（进阶优化）

题目三：最长连续序列

问题介绍

基础示例

问题分析

思路：哈希集合法

题目四：无重复字符的最长子串

问题介绍

基础示例

问题分析

思路一：暴力枚举（不推荐）

思路二：滑动窗口 + 哈希集合（基础解法）

思路三：滑动窗口 + 哈希映射（优化解法）

题目五：字符串所有字母异位词

问题介绍

基础示例

问题分析

思路一：暴力枚举（不推荐）

思路二：滑动窗口 + 数组计数（最优解）

思路三：滑动窗口 + 差异变量优化（进阶思想）

题目六：和为 K 的子数组

问题介绍

基础示例

问题分析

思路一：暴力枚举（不推荐）

思路二：前缀和 + 哈希表优化（最优解）

题目七：最小覆盖子串

问题介绍

基础示例

问题分析

思路一：暴力枚举（不推荐）

思路二：可变滑动窗口 + 哈希表（最优解，满足进阶 O(m+n)O(m+n)O(m+n) 要求）

总结：哈希类题目的通用解题思路

核心思想

通用解题套路

思路二：可变滑动窗口 + 哈希表（最优解，满足进阶 $O(m+n)$ 要求）