哈希算法题目：寻找字符串中所有变位词
字数 3795 2025-12-14 12:05:24

哈希算法题目：寻找字符串中所有变位词

题目描述

给你一个字符串 s 和一个非空字符串 p。请你找出 s 中所有是 p 的变位词（即字母异位词，由相同字母重排形成的子串，包括 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" 的变位词。

提示：

  • 字符串 s 和 p 仅包含小写英文字母。
  • 1 <= p.length <= s.length <= 3 * 10^4

解题过程循序渐进讲解

步骤1：理解问题的核心

我们需要在字符串 s 中，找到所有长度等于 p 的子串，这些子串是 p 的字母异位词。字母异位词意味着两个字符串包含的字母种类和每个字母的数量完全相同，只是排列顺序不同。

关键点：比较两个字符串是否为字母异位词，不需要关心顺序，只需比较它们所含字符的频率是否一致。例如，"abc" 和 "cba" 的字符频率都是 {'a':1, 'b':1, 'c':1}。

步骤2：基础思路与暴力法

最直接的想法是：

  1. 计算字符串 p 的字符频率分布。
  2. 遍历 s 中所有长度为 len(p) 的子串。
  3. 对每个子串，计算其字符频率，并与 p 的频率分布比较。
  4. 如果完全一致，则记录当前子串的起始索引。

复杂度分析：

  • 假设 n = len(s), m = len(p)。
  • 有 n - m + 1 个子串。
  • 每次比较频率分布需要检查最多26个小写字母（常数时间），但计算子串频率需要 O(m) 时间。
  • 总时间复杂度 O((n - m + 1) * m) ≈ O(n * m)，在 m 较大时效率低下。

我们需要一个更高效的方法。

步骤3：引入哈希表与滑动窗口

为了优化，我们可以利用滑动窗口和哈希表。

核心思想：

  1. 用一个固定大小的窗口（长度 = m）在 s 上滑动。
  2. 用两个哈希表（或长度为26的数组，因为只有小写字母）分别记录：
    • pCount：字符串 p 的字符频率。
    • sWindowCount：当前窗口中 s 子串的字符频率。
  3. 当窗口滑动时，我们增量式更新 sWindowCount，而不是每次重新计算整个子串的频率。这样，更新窗口的频率只需要 O(1) 时间。

如何增量更新？

  • 窗口向右滑动一位时：
    • 新进入窗口的字符：频率加1。
    • 离开窗口的字符（左边界的字符）：频率减1。
  • 每次窗口移动后，比较 pCount 和 sWindowCount 是否相等。相等则说明当前窗口是变位词，记录起始索引。

步骤4：算法步骤详解

假设我们用两个长度为26的数组 pCount 和 sWindowCount 来表示频率（索引0对应'a'，1对应'b'，...，25对应'z'）。

  1. 初始化：

    • 计算 p 的频率数组 pCount。
    • 计算 s 的前 m 个字符（第一个窗口）的频率数组 sWindowCount。
    • 比较 pCount 和 sWindowCount，如果相等，则索引0是一个答案。

  2. 滑动窗口（i 从1 到 n - m，i 是窗口起始索引）：

    • 移除字符：离开窗口的字符是 s[i-1]，将 sWindowCount[s[i-1] - 'a'] 减1。
    • 新增字符：进入窗口的字符是 s[i + m - 1]，将 sWindowCount[s[i + m - 1] - 'a'] 加1。
    • 比较 pCount 和 sWindowCount，如果相等，则当前起始索引 i 是一个答案。

  3. 返回结果列表。

举例：s = "cbaebabacd", p = "abc"

  • m = 3, n = 10。
  • 初始化 pCount = {'a':1, 'b':1, 'c':1}，第一个窗口 "cba" 的 sWindowCount = {'a':1, 'b':1, 'c':1}，相等 → 记录索引0。
  • 窗口滑动到索引1（"bae"）：
    • 移除 'c'，加入 'e' → sWindowCount = {'a':1, 'b':1, 'e':1}，与 pCount 不等。
  • 继续滑动...直到窗口 "bac"（索引6）：
    • 此时 sWindowCount = {'a':1, 'b':1, 'c':1}，与 pCount 相等 → 记录索引6。

步骤5：优化比较操作

每次窗口移动后，我们需要比较两个长度为26的数组是否相等。如果直接比较，需要26次操作，虽然是常数时间，但我们可以进一步优化。

引入一个 match 变量：

  • 我们只关心两个频率数组是否完全一致。可以维护一个计数器 match，表示 pCount 和 sWindowCount 中有多少个字符的频率是匹配的（即该字符在两者中的计数相等）。
  • 初始时，计算 pCount 和第一个窗口的 sWindowCount，并统计 match 的数量（频率相等的字符数）。
  • 当窗口滑动时，只更新受影响的字符的频率，并更新 match：
    • 移除一个字符 leftChar：
      • 如果该字符在滑动前，pCount[leftChar] == sWindowCount[leftChar]，则匹配数减1（因为移除后就不等了）。
      • 更新 sWindowCount[leftChar] 减1。
      • 如果更新后，pCount[leftChar] == sWindowCount[leftChar]，则匹配数加1。
    • 新增一个字符 rightChar：
      • 采用类似逻辑更新 match。
  • 每次窗口更新后，如果 match == 26，说明所有字符频率都匹配，当前窗口是变位词。

这样，我们避免了每次比较整个数组，而是用 O(1) 时间维护 match。

步骤6：最终算法步骤

  1. 如果 len(p) > len(s)，直接返回空列表。
  2. 初始化数组 pCount 和 sWindowCount（长度26），初始值为0。
  3. 遍历 p 的每个字符，更新 pCount。
  4. 遍历 s 的前 m 个字符，更新 sWindowCount。
  5. 初始化 match = 0，遍历0到25，如果 pCount[i] == sWindowCount[i]，则 match++。
  6. 初始化结果列表 result = []。
  7. 遍历窗口起始索引 i 从 0 到 n - m：
    • 如果 match == 26，将 i 加入 result。
    • 如果 i == n - m，跳出循环（最后一个窗口已检查）。
    • 处理窗口滑动：
      • 移除字符 left = s[i]，按照步骤5的逻辑更新 match 和 sWindowCount。
      • 新增字符 right = s[i + m]，按照步骤5的逻辑更新 match 和 sWindowCount。
  8. 返回 result。

步骤7：复杂度分析

  • 时间：O(n)。每个字符最多进入和离开窗口各一次，每次更新 match 是 O(1)，总操作次数与 n 线性相关。
  • 空间：O(1)。只用了两个长度26的数组和几个变量，与输入规模无关。

步骤8：示例 walkthrough

以 s = "abab", p = "ab" 为例：

  • n=4, m=2.
  • pCount: a:1, b:1.
  • 初始窗口 (i=0): "ab", sWindowCount: a:1, b:1. match=26 → 记录0.
  • 滑动到 i=1:
    • 移除 s[0]='a' → 更新后 sWindowCount: a:0, b:1 → match 更新后=25（只有b匹配）。
    • 新增 s[2]='a' → 更新后 sWindowCount: a:1, b:1 → match 更新后=26 → 记录1.
  • 滑动到 i=2:
    • 移除 s[1]='b' → sWindowCount: a:1, b:0 → match=25.
    • 新增 s[3]='b' → sWindowCount: a:1, b:1 → match=26 → 记录2.
  • 结果: [0,1,2].

总结

本题的核心是利用哈希表（数组）记录字符频率，结合滑动窗口实现线性时间内的变位词搜索。通过维护 match 变量，我们进一步优化了比较效率。这是一个经典的“哈希表+滑动窗口”组合应用，在字符串匹配和子串搜索问题中非常常见。

哈希算法题目：寻找字符串中所有变位词 题目描述 给你一个字符串 s 和一个非空字符串 p 。请你找出 s 中所有是 p 的变位词（即字母异位词，由相同字母重排形成的子串，包括 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" 的变位词。 提示： 字符串 s 和 p 仅包含小写英文字母。 1 <= p.length <= s.length <= 3 * 10^4 解题过程循序渐进讲解 步骤1：理解问题的核心 我们需要在字符串 s 中，找到所有长度等于 p 的子串，这些子串是 p 的 字母异位词 。字母异位词意味着两个字符串包含的字母种类和每个字母的数量完全相同，只是排列顺序不同。 关键点 ：比较两个字符串是否为字母异位词，不需要关心顺序，只需比较它们所含字符的 频率 是否一致。例如， "abc" 和 "cba" 的字符频率都是 {'a':1, 'b':1, 'c':1} 。 步骤2：基础思路与暴力法 最直接的想法是： 计算字符串 p 的字符频率分布。 遍历 s 中所有长度为 len(p) 的子串。 对每个子串，计算其字符频率，并与 p 的频率分布比较。 如果完全一致，则记录当前子串的起始索引。 复杂度分析 ： 假设 n = len(s) , m = len(p) 。 有 n - m + 1 个子串。 每次比较频率分布需要检查最多26个小写字母（常数时间），但计算子串频率需要 O(m) 时间。 总时间复杂度 O((n - m + 1) * m) ≈ O(n * m)，在 m 较大时效率低下。 我们需要一个更高效的方法。 步骤3：引入哈希表与滑动窗口 为了优化，我们可以利用 滑动窗口 和 哈希表 。 核心思想 ： 用一个固定大小的窗口（长度 = m ）在 s 上滑动。 用两个哈希表（或长度为26的数组，因为只有小写字母）分别记录： pCount ：字符串 p 的字符频率。 sWindowCount ：当前窗口中 s 子串的字符频率。 当窗口滑动时，我们 增量式更新 sWindowCount ，而不是每次重新计算整个子串的频率。这样，更新窗口的频率只需要 O(1) 时间。 如何增量更新 ？ 窗口向右滑动一位时： 新进入窗口的字符：频率加1。 离开窗口的字符（左边界的字符）：频率减1。 每次窗口移动后，比较 pCount 和 sWindowCount 是否相等。相等则说明当前窗口是变位词，记录起始索引。 步骤4：算法步骤详解 假设我们用两个长度为26的数组 pCount 和 sWindowCount 来表示频率（索引0对应'a'，1对应'b'，...，25对应'z'）。 初始化 ： 计算 p 的频率数组 pCount 。 计算 s 的前 m 个字符（第一个窗口）的频率数组 sWindowCount 。 比较 pCount 和 sWindowCount ，如果相等，则索引0是一个答案。 滑动窗口 （ i 从1 到 n - m ， i 是窗口起始索引）： 移除字符：离开窗口的字符是 s[i-1] ，将 sWindowCount[s[i-1] - 'a'] 减1。 新增字符：进入窗口的字符是 s[i + m - 1] ，将 sWindowCount[s[i + m - 1] - 'a'] 加1。 比较 pCount 和 sWindowCount ，如果相等，则当前起始索引 i 是一个答案。 返回结果列表 。 举例 ：s = "cbaebabacd", p = "abc" m = 3, n = 10。 初始化 pCount = {'a':1, 'b':1, 'c':1} ，第一个窗口 "cba" 的 sWindowCount = {'a':1, 'b':1, 'c':1} ，相等 → 记录索引0。 窗口滑动到索引1（"bae"）： 移除 'c'，加入 'e' → sWindowCount = {'a':1, 'b':1, 'e':1} ，与 pCount 不等。 继续滑动...直到窗口 "bac"（索引6）： 此时 sWindowCount = {'a':1, 'b':1, 'c':1} ，与 pCount 相等 → 记录索引6。 步骤5：优化比较操作 每次窗口移动后，我们需要比较两个长度为26的数组是否相等。如果直接比较，需要26次操作，虽然是常数时间，但我们可以进一步优化。 引入一个 match 变量 ： 我们只关心两个频率数组是否完全一致。可以维护一个计数器 match ，表示 pCount 和 sWindowCount 中有多少个字符的频率是匹配的（即该字符在两者中的计数相等）。 初始时，计算 pCount 和第一个窗口的 sWindowCount ，并统计 match 的数量（频率相等的字符数）。 当窗口滑动时，只更新受影响的字符的频率，并更新 match ： 移除一个字符 leftChar ： 如果该字符在滑动 前 ， pCount[leftChar] == sWindowCount[leftChar] ，则匹配数减1（因为移除后就不等了）。 更新 sWindowCount[leftChar] 减1。 如果更新后， pCount[leftChar] == sWindowCount[leftChar] ，则匹配数加1。 新增一个字符 rightChar ： 采用类似逻辑更新 match 。 每次窗口更新后，如果 match == 26 ，说明所有字符频率都匹配，当前窗口是变位词。 这样，我们 避免了每次比较整个数组 ，而是用 O(1) 时间维护 match 。 步骤6：最终算法步骤 如果 len(p) > len(s) ，直接返回空列表。 初始化数组 pCount 和 sWindowCount （长度26），初始值为0。 遍历 p 的每个字符，更新 pCount 。 遍历 s 的前 m 个字符，更新 sWindowCount 。 初始化 match = 0 ，遍历0到25，如果 pCount[i] == sWindowCount[i] ，则 match++ 。 初始化结果列表 result = [] 。 遍历窗口起始索引 i 从 0 到 n - m ： 如果 match == 26 ，将 i 加入 result 。 如果 i == n - m ，跳出循环（最后一个窗口已检查）。 处理窗口滑动： 移除字符 left = s[i] ，按照步骤5的逻辑更新 match 和 sWindowCount 。 新增字符 right = s[i + m] ，按照步骤5的逻辑更新 match 和 sWindowCount 。 返回 result 。 步骤7：复杂度分析 时间：O(n)。每个字符最多进入和离开窗口各一次，每次更新 match 是 O(1)，总操作次数与 n 线性相关。 空间：O(1)。只用了两个长度26的数组和几个变量，与输入规模无关。 步骤8：示例 walkthrough 以 s = "abab", p = "ab" 为例： n=4, m=2. pCount: a:1, b:1. 初始窗口 (i=0): "ab", sWindowCount: a:1, b:1. match=26 → 记录0. 滑动到 i=1: 移除 s[ 0 ]='a' → 更新后 sWindowCount: a:0, b:1 → match 更新后=25（只有b匹配）。 新增 s[ 2 ]='a' → 更新后 sWindowCount: a:1, b:1 → match 更新后=26 → 记录1. 滑动到 i=2: 移除 s[ 1 ]='b' → sWindowCount: a:1, b:0 → match=25. 新增 s[ 3 ]='b' → sWindowCount: a:1, b:1 → match=26 → 记录2. 结果: [ 0,1,2 ]. 总结 本题的核心是 利用哈希表（数组）记录字符频率，结合滑动窗口实现线性时间内的变位词搜索 。通过维护 match 变量，我们进一步优化了比较效率。这是一个经典的“哈希表+滑动窗口”组合应用，在字符串匹配和子串搜索问题中非常常见。