企业官网建设流程全解析

目录

一、题目解析

二、讲解算法原理

解法一：暴力枚举 + 哈希表

解法二：滑动窗口 + 哈希表

优化：判断条件

三、代码实现

大家好，今天我们来攻克 LeetCode 上的一道经典难题——76. 最小覆盖子串。这道题是滑动窗口算法的典型应用，结合了哈希表来优化判断过程。

一、题目解析

题目：​ 给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。

注意：

1. 对于t中重复字符，我们寻找的子串中该字符数量必须不少于t中该字符数量。

2. 如果s中存在这样的子串，我们保证它是唯一的答案。

示例 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的子串中，因此没有符合条件的子子串，返回空字符串。

二、讲解算法原理

解法一：暴力枚举 + 哈希表

解法二：滑动窗口 + 哈希表

这是本题的最优解。核心思想是维护一个窗口[left, right]，通过移动左右指针来寻找最小覆盖子串。

• 核心逻辑：

  1. right 右移：​ 不断扩大窗口，直到窗口包含了t中的所有字符。

  2. left 右移：​ 在满足覆盖条件的前提下，尝试缩小窗口左边界，以找到最小长度。

优化：判断条件

为了优化每次判断窗口是否覆盖t的时间复杂度，我们可以引入一个变量count。

• 思路：​ 使用变量count标记有效字符的种类。

  • 进窗口：​ 当hash2[in] == hash1[in]时，count++。

  • 出窗口：​ 当hash2[out] == hash1[out]时，count--。

  • 判断条件：​ 当count == hash1.size()时，说明窗口已覆盖t。

三、代码实现

class Solution { public String minWindow(String ss, String tt) { char[] s = ss.toCharArray(); char[] t = tt.toCharArray(); int[] hash1 = new int[128]; // 统计字符串 t 中字符的频次 int kinds = 0; // 字符串 t 中，有多少种字符 for(char ch : t) { if(hash1[ch]++ == 0) kinds++; } int[] hash2 = new int[128]; // 统计窗口中字符的频次 int minlen = Integer.MAX_VALUE, begin = -1; for(int left = 0, right = 0, count = 0; right < s.length; right++) { char in = s[right]; if(++hash2[in] == hash1[in]) count++; // 进窗口 + 维护 count while(kinds == count) // 判断 { // 更新结果 if(right - left + 1 < minlen) { begin = left; minlen = right - left + 1; } char out = s[left++]; if(hash2[out]-- == hash1[out]) count--; // 出窗口 + 维护 count } } if(begin == -1) return new String(); else return ss.substring(begin, begin + minlen); } }