企业官网建设流程全解析

一、面试问题

给定两个字符串s和p，任务是找到s中包含p中所有字符（包含重复字符）的最小子串。如果不存在这样的子串，返回空字符串""。如果找到多个长度相同的符合条件的子串，返回起始下标最小的那一个。

示例 1：

输入：s = "timetopractice"，p = "toc"

输出：toprac

解释："toprac" 是包含 "toc" 所有字符的最小子串。

示例 2：

输入：s = "zoomlazapzo"，p = "oza"

输出：apzo

解释："apzo" 是包含 "oza" 所有字符的最小子串。

二、【朴素解法】通过生成所有子串实现 —— 时间复杂度 O (n³)，空间复杂度 O (n)

(一) 解法思路

解决这个问题最基础的思路是：我们可以生成给定字符串s的所有可能子串，并逐一检查每个子串是否包含字符串p的全部字符。这项检查可以通过一个辅助函数完成，该函数会对比p中每个字符的出现次数与所选子串中对应字符的频次是否一致。如果某个子串包含了p的所有字符，就将它的长度与当前记录的最小长度比较，并相应更新最小子串。这一过程会持续进行，直到所有子串都被检查完毕。

(二) 使用 5 种语言实现

1. C++

#include <climits> #include <iostream> #include <string> using namespace std; // 辅助函数：检查子串 sub 是否包含 p 中所有字符（含数量） bool hasAllChars(string &sub, string &p) { int count[256] = {0}; // 用数组统计所有ASCII字符的频次 // 第一步：统计模式串 p 中每个字符的出现次数 for (char ch : p) count[ch]++; // 第二步：遍历子串，抵消对应字符的计数 for (char ch : sub) { if (count[ch] > 0) count[ch]--; } // 第三步：如果所有计数都为0，说明子串满足条件 for (int i = 0; i < 256; i++) { if (count[i] > 0) return false; } return true; } // 主函数：寻找 s 中包含 p 所有字符的最小子串 string minWindow(string &s, string &p) { int n = s.length(); int minLen = INT_MAX; // 记录最小长度 string res = ""; // 记录最终结果 // 双重循环：生成 s 的所有子串 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // 截取从 i 开始，长度为 j-i+1 的子串 string sub = s.substr(i, j - i + 1); // 检查当前子串是否符合要求 if (hasAllChars(sub, p)) { int currLen = sub.length(); // 如果当前子串更短，更新最小值和结果 if (currLen < minLen) { minLen = currLen; res = sub; } } } } return res; } // 主程序测试 int main() { string s = "timetopractice"; string p = "toc"; string res = minWindow(s, p); if (!res.empty()) cout << res << endl; // 输出：toprac else cout << "" << endl; return 0; }

2. Java

class DSA { // 辅助函数：检查子串 sub 是否包含 p 中所有字符（数量也要匹配） static boolean hasAllChars(String sub, String p) { int[] count = new int[256]; // 用数组统计 ASCII 字符频次 // 第一步：统计模式串 p 中每个字符的出现次数 for (int i = 0; i < p.length(); i++) { count[p.charAt(i)]++; } // 第二步：遍历子串，抵消对应字符的计数 for (int i = 0; i < sub.length(); i++) { if (count[sub.charAt(i)] > 0) count[sub.charAt(i)]--; } // 第三步：如果还有计数 > 0，说明缺少字符，返回 false for (int i = 0; i < 256; i++) { if (count[i] > 0) return false; } return true; } // 主函数：寻找 s 中包含 p 所有字符的最小子串 static String minWindow(String s, String p) { int n = s.length(); int minLen = Integer.MAX_VALUE; // 记录最小长度 String res = ""; // 记录最终结果 // 双重循环：生成所有子串 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // 截取子串 [i, j+1) → 对应从 i 到 j String sub = s.substring(i, j + 1); // 检查是否满足条件 if (hasAllChars(sub, p)) { int currLen = sub.length(); // 如果当前子串更短，更新结果 if (currLen < minLen) { minLen = currLen; res = sub; } } } } return res; } // 测试主函数 public static void main(String[] args) { String s = "timetopractice"; String p = "toc"; String result = minWindow(s, p); if (!result.isEmpty()) System.out.println(result); // 输出：toprac else System.out.println(""); } }

3. Python

def hasallchars(s: str, p: str) -> bool: count = [0] * 256 # 统计所有 ASCII 字符的出现次数 # 统计模式串 p 中每个字符的频次 for ch in p: count[ord(ch)] += 1 # 用子串 s 的字符抵消计数 for ch in s: if count[ord(ch)] > 0: count[ord(ch)] -= 1 # 如果还有剩余计数，说明不满足条件 for val in count: if val > 0: return False return True # 查找 s 中包含 p 所有字符的最小子串 def minWindow(s: str, p: str) -> str: n = len(s) minLen = float('inf') # 记录最小长度 result = "" # 保存最终答案 # 双重循环：生成所有子串 for i in range(n): for j in range(i, n): sub = s[i:j + 1] # 截取子串 # 检查是否包含 p 的全部字符 if hasallchars(sub, p): currLen = len(sub) # 更新最小子串 if currLen < minLen: minLen = currLen result = sub return result # 测试 if __name__ == "__main__": s = "timetopractice" p = "toc" res = minWindow(s, p) print(res) # 输出：toprac

4. C#

using System; class DSA { // 辅助函数：检查子串 s 是否包含模式串 p 的所有字符（包含重复次数） static bool hasAllChars(string s, string p) { int[] count = new int[256]; // 存储ASCII字符的频次 // 统计模式串 p 中每个字符的出现次数 foreach (char ch in p) count[ch]++; // 遍历子串，抵消对应字符的计数 foreach (char ch in s) { if (count[ch] > 0) count[ch]--; } // 检查是否所有字符计数都为0，是则说明满足条件 for (int i = 0; i < 256; i++) { if (count[i] > 0) return false; } return true; } // 主函数：寻找字符串 s 中包含 p 所有字符的最小子串 static string minWindow(string s, string p) { int n = s.Length; int minLen = int.MaxValue; // 记录最小长度 string result = ""; // 存储最终结果 // 双重循环：生成 s 的所有子串 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // 截取从索引 i 开始，长度为 j-i+1 的子串 string sub = s.Substring(i, j - i + 1); // 检查当前子串是否符合要求 if (hasAllChars(sub, p)) { int currLen = sub.Length; // 如果当前子串更短，更新最小长度和结果 if (currLen < minLen) { minLen = currLen; result = sub; } } } } return result; } // 主函数，程序入口 static void Main() { string s = "timetopractice"; string p = "toc"; string res = minWindow(s, p); if (!string.IsNullOrEmpty(res)) Console.WriteLine(res); // 输出：toprac else Console.WriteLine(""); } }

5. JavaScript

// 辅助函数：检查子串 s 是否包含 p 中所有字符（数量也要匹配） function hasAllChars(s, p) { const count = new Array(256).fill(0); // ASCII 字符频次数组 // 统计模式串 p 的字符频次 for (let ch of p) { count[ch.charCodeAt(0)]++; } // 用子串 s 的字符抵消频次 for (let ch of s) { if (count[ch.charCodeAt(0)] > 0) { count[ch.charCodeAt(0)]--; } } // 所有计数 = 0 → 满足条件 for (let val of count) { if (val > 0) { return false; } } return true; } // 主函数：寻找 s 中包含 p 所有字符的最小子串 function minWindow(s, p) { const n = s.length; let minLen = Infinity; // 记录最小长度 let result = ""; // 保存最终结果 // 双重循环：生成所有子串 for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { const sub = s.substring(i, j + 1); // 截取子串 // 检查是否符合条件 if (hasAllChars(sub, p)) { const currLen = sub.length; // 更新最小子串 if (currLen < minLen) { minLen = currLen; result = sub; } } } } return result; } // 测试代码 const s = "timetopractice"; const p = "toc"; const res = minWindow(s, p); if (res.length > 0) { console.log(res); // 输出：toprac } else { console.log("-1"); }

(三)代码输出和算法复杂度

输出：

toprac

时间复杂度：O(n³)

空间复杂度：O(1)

三、【优化解法】通过二分答案实现 —— 时间复杂度 O (n*log (n))，空间复杂度 O (1)

(一) 解法思路

核心思路是：检查某个长度为 mid 的窗口是否有效（包含 p 串的所有字符）。如果长度为mid的窗口有效，那么所有比 mid 更长的窗口也一定有效；同理，如果长度为mid的窗口无效，那么所有比 mid 更短的窗口也一定无效。这个特性让我们可以高效地使用二分查找。

按照以下步骤解决问题：

1. 初始化low = 1，high = 字符串 s 的长度，分别表示答案的最小、最大可能长度。
2. 对于任意中间值mid，检查字符串s中是否存在长度为 mid 的子串，包含p的所有字符。
3. 如果存在这样的子串：

• • 记录该子串的起始下标
  • 将high更新为mid - 1，继续寻找比 mid 更短的有效子串

1. 如果不存在这样的子串：

• • 将low更新为mid + 1，继续寻找比 mid 更长的子串

(二) 使用 5 种语言实现

1. C++

#include <iostream> #include <string> #include <climits> #include <cstring> using namespace std; // 检查：s 中是否存在长度为 mid 的窗口，包含 p 所有字符 // start 用于记录满足条件的窗口起始位置 bool isValid(string &s, string &p, int mid, int &start) { int count[256] = {0}; int distinct = 0; // p 中不同字符的数量 // 统计 p 中每个字符的频次 + 统计不同字符总数 for (char x : p) { if (count[x] == 0) distinct++; count[x]++; } int curr_count = 0; // 当前窗口满足频次要求的字符数量 // 滑动窗口遍历 s for (int i = 0; i < s.size(); i++) { // 加入当前字符 count[s[i]]--; if (count[s[i]] == 0) { curr_count++; } // 窗口超过 mid 长度，移除左边的字符 if (i >= mid) { count[s[i - mid]]++; if (count[s[i - mid]] == 1) { curr_count--; } } // 窗口长度达到 mid，检查是否满足条件 if (i >= mid - 1) { if (curr_count == distinct) { start = i - mid + 1; // 记录起始位置 return true; } } } return false; } // 二分查找找最小窗口 string minWindow(string s, string p) { int m = s.length(); int n = p.length(); // s 比 p 短，不可能找到 if (m < n) return "-1"; int minLength = INT_MAX; int idx = -1; // 答案起始下标 // 二分范围：最小 n，最大 m int low = n, high = m; while (low <= high) { int mid = (low + high) / 2; int start; // 找到长度为 mid 的有效窗口 → 尝试更小的 if (isValid(s, p, mid, start)) { minLength = mid; idx = start; high = mid - 1; } // 没找到 → 需要更大窗口 else { low = mid + 1; } } if (idx == -1) return ""; return s.substr(idx, minLength); } // 主函数测试 int main() { string s = "timetopractice"; string p = "toc"; cout << minWindow(s, p) << endl; // 输出：toprac return 0; }

2. Java

import java.util.HashMap; class DSA { // 检查 s 中是否存在长度为 mid 的有效窗口（包含 p 所有字符） // start[0] 用于传回满足条件的起始索引 public static boolean isValid(String s, String p, int mid, int[] start) { int[] count = new int[256]; // 统计 ASCII 字符频次 int distinct = 0; // p 中**不同字符**的数量 // 第一步：统计 p 中每个字符的频次，并统计有多少种不同字符 for (char x : p.toCharArray()) { if (count[x] == 0) distinct++; count[x]++; } int currCount = 0; // 当前窗口中，频次满足 p 要求的字符数 // 滑动窗口遍历字符串 s for (int i = 0; i < s.length(); i++) { // 把当前字符加入窗口 count[s.charAt(i)]--; if (count[s.charAt(i)] == 0) { currCount++; } // 窗口长度超过 mid，移除最左边的字符 if (i >= mid) { count[s.charAt(i - mid)]++; if (count[s.charAt(i - mid)] == 1) { currCount--; } } // 窗口长度达到 mid，检查是否有效 if (i >= mid - 1 && currCount == distinct) { start[0] = i - mid + 1; // 记录有效窗口起点 return true; } } return false; } // 主函数：二分查找最小窗口 public static String minWindow(String s, String p) { int m = s.length(); int n = p.length(); // s 比 p 短，直接返回空 if (m < n) return ""; int low = n, high = m; // 二分范围：最短 n，最长 m int[] start = new int[1]; // 用于传回起点 int minLength = Integer.MAX_VALUE; // 二分查找最优长度 while (low <= high) { int mid = (low + high) / 2; // 找到有效窗口 → 尝试更小长度 if (isValid(s, p, mid, start)) { minLength = mid; high = mid - 1; } // 无效 → 需要更大窗口 else { low = mid + 1; } } // 没找到答案 if (minLength == Integer.MAX_VALUE) return ""; // 截取结果 return s.substring(start[0], start[0] + minLength); } // 测试主函数 public static void main(String[] args) { String s = "timetopractice"; String p = "toc"; System.out.println(minWindow(s, p)); // 输出：toprac } }

3. Python

def isValid(s, p, mid): count = [0] * 256 # ASCII 字符频次统计数组 distinct = 0 # p 中不同字符的种类数量 # 统计模式串 p 中每个字符的频次 + 统计不同字符数 for x in p: if count[ord(x)] == 0: distinct += 1 count[ord(x)] += 1 curr_count = 0 # 当前窗口满足频次要求的字符种类数 # 滑动窗口遍历主串 s for i in range(len(s)): # 把当前字符加入窗口 count[ord(s[i])] -= 1 if count[ord(s[i])] == 0: curr_count += 1 # 窗口超过长度 mid，移除左侧字符 if i >= mid: count[ord(s[i - mid])] += 1 if count[ord(s[i - mid])] == 1: curr_count -= 1 # 窗口长度达到 mid，检查是否满足条件 if i >= mid - 1: if curr_count == distinct: return True, i - mid + 1 # 返回有效 + 起始位置 return False, -1 # 未找到有效窗口 def minWindow(s, p): m = len(s) n = len(p) # 主串比模式串短，直接返回空 if m < n: return "" minLength = float('inf') low, high = n, m # 二分范围：最小 n，最大 m idx = -1 # 记录最终答案起始索引 # 二分查找最小有效窗口长度 while low <= high: mid = (low + high) // 2 valid, start = isValid(s, p, mid) if valid: # 找到有效窗口，尝试更小长度 if mid < minLength: minLength = mid idx = start high = mid - 1 else: # 无效，需要更大窗口 low = mid + 1 if idx == -1: return "" # 截取结果子串 return s[idx:idx + minLength] # 测试 if __name__ == "__main__": s = "timetopractice" p = "toc" print(minWindow(s, p)) # 输出：toprac

4. C#

using System; class DSA { /// <summary> /// 检查字符串 s 中是否存在长度为 mid 的窗口，包含 p 的所有字符 /// </summary> /// <param name="start">输出：满足条件的窗口起始索引</param> static bool IsValid(string s, string p, int mid, out int start) { int[] count = new int[256]; // ASCII 字符频次数组 int distinct = 0; // p 中不同字符的种类数 start = -1; // 统计 p 中每个字符的频次，并统计不同字符数量 foreach (char x in p) { if (count[x] == 0) distinct++; count[x]++; } int currCount = 0; // 当前窗口满足频次要求的字符种类数 // 滑动窗口遍历 s for (int i = 0; i < s.Length; i++) { // 加入当前字符 count[s[i]]--; if (count[s[i]] == 0) currCount++; // 窗口超过 mid 长度，移除左侧字符 if (i >= mid) { count[s[i - mid]]++; if (count[s[i - mid]] == 1) currCount--; } // 窗口长度达到 mid，检查是否有效 if (i >= mid - 1) { if (currCount == distinct) { start = i - mid + 1; return true; } } } return false; } /// <summary> /// 二分查找最小窗口子串 /// </summary> static string minWindow(string s, string p) { int m = s.Length; int n = p.Length; // s 比 p 短，直接返回空 if (m < n) return ""; int minLength = int.MaxValue; int low = n, high = m; // 二分范围：最短 n，最长 m int idx = -1; // 答案起始位置 // 二分查找最优长度 while (low <= high) { int mid = (low + high) / 2; int start; // 找到有效窗口 → 尝试更小长度 if (IsValid(s, p, mid, out start)) { if (mid < minLength) { minLength = mid; idx = start; } high = mid - 1; } // 无效 → 需要更大窗口 else { low = mid + 1; } } if (idx == -1) return ""; // 截取结果 return s.Substring(idx, minLength); } // 测试主函数 static void Main() { string s = "timetopractice"; string p = "toc"; Console.WriteLine(minWindow(s, p)); // 输出：toprac } }

5. JavaScript

// 检查 s 中是否存在长度为 mid 的有效窗口，包含 p 所有字符 // 返回：有效则返回起始索引，无效返回 -1 function isValid(s, p, mid) { const count = new Array(256).fill(0); // ASCII 字符频次 let distinct = 0; // p 中不同字符的种类数 // 统计 p 中每个字符的频次 + 统计不同字符数量 for (let x of p) { const code = x.charCodeAt(0); if (count[code] === 0) distinct++; count[code]++; } let currCount = 0; // 当前窗口满足频次要求的字符数 let start = -1; // 滑动窗口遍历 s for (let i = 0; i < s.length; i++) { const code = s[i].charCodeAt(0); count[code]--; if (count[code] === 0) { currCount++; } // 窗口超过长度 mid，移除左侧字符 if (i >= mid) { const leftCode = s[i - mid].charCodeAt(0); count[leftCode]++; if (count[leftCode] === 1) { currCount--; } } // 窗口长度达到 mid，检查是否有效 if (i >= mid - 1) { if (currCount === distinct) { start = i - mid + 1; return start; } } } return -1; } // 二分查找最小窗口 function minWindow(s, p) { const m = s.length; const n = p.length; // s 比 p 短，直接返回空 if (m < n) return ""; let minLength = Infinity; let low = n, high = m; // 二分范围：最小 n，最大 m let idx = -1; // 最终答案起始位置 // 二分查找最小有效长度 while (low <= high) { const mid = Math.floor((low + high) / 2); const start = isValid(s, p, mid); if (start !== -1) { // 找到有效窗口，尝试更小长度 if (mid < minLength) { minLength = mid; idx = start; } high = mid - 1; } else { // 无效，需要更大窗口 low = mid + 1; } } if (idx === -1) return ""; // 截取结果 return s.substring(idx, idx + minLength); } // 测试代码 const s = "timetopractice"; const p = "toc"; console.log(minWindow(s, p)); // 输出：toprac

(三)代码输出和算法复杂度

输出：

toprac

时间复杂度：(n*log (n))

空间复杂度：O(1)

四、【最优解法】采用滑动窗口 —— 时间复杂度 O (n)，空间复杂度 O (1)

(一) 解法思路

核心思路是利用滑动窗口（使用左指针start和右指针j）在字符串S上维护一个动态窗口，同时用两个字符频次数组来跟踪字符出现次数。

步骤：

① 初始化：

• 一个计数数组，用于存储模式串P中各字符的出现频次。
• 另一个计数数组，用于跟踪字符串S当前窗口内的字符。
• 若干变量，用于记录最小窗口长度及其起始下标。

② 扩展窗口：

• 移动右指针j遍历字符串 S，同时更新当前窗口内的字符计数。
• 当窗口中已包含 P 的所有字符时，说明找到了一个有效窗口。

③ 在更新结果前收缩窗口：

• 向右移动左指针start，尽可能缩小窗口，同时保证窗口内仍包含 P 的所有字符。
• 在此过程中记录最小的窗口。

⑥ 返回结果：

• 若找到有效窗口，返回最小子串；若不存在，则返回"-1"。

(二) 使用 5 种语言实现

1. C++

#include <iostream> #include <string> #include <vector> #include <climits> using namespace std; // 最优解法：滑动窗口（双指针） // 时间 O(n)，空间 O(1) string minWindow(string s, string p) { int len1 = s.length(); int len2 = p.length(); // 如果 s 比 p 短，直接返回空 if (len1 < len2) return ""; vector<int> countP(256, 0); // 存储 p 的字符频次 vector<int> countS(256, 0); // 存储当前窗口的字符频次 // 统计模式串 p 中所有字符的出现次数 for (int i = 0; i < len2; i++) countP[p[i]]++; int start = 0; // 窗口左指针 int start_idx = -1; // 最小窗口的起始位置 int min_len = INT_MAX; // 最小窗口长度 int matchCount = 0; // 已匹配的字符数量（达到 len2 表示窗口有效） // 右指针 j 扩展窗口 for (int j = 0; j < len1; j++) { // 当前字符加入窗口 countS[s[j]]++; // 如果这个字符是 p 需要的，且数量没超，就记为有效匹配 if (countP[s[j]] != 0 && countS[s[j]] <= countP[s[j]]) { matchCount++; } // ======================== // 窗口已包含所有 p 字符 → 尝试收缩左边界，缩小窗口 // ======================== while (matchCount == len2) { // 1. 尝试把左指针往右移，缩小窗口 while (countS[s[start]] > countP[s[start]] || countP[s[start]] == 0) { if (countS[s[start]] > countP[s[start]]) countS[s[start]]--; start++; } // 2. 更新最小窗口 int currWindowLen = j - start + 1; if (min_len > currWindowLen) { min_len = currWindowLen; start_idx = start; } // 3. 移动左指针，尝试继续收缩（退出循环用） countS[s[start]]--; matchCount--; start++; } } // 没找到返回空 if (start_idx == -1) return ""; // 返回最小窗口子串 return s.substr(start_idx, min_len); } // 测试 int main() { string s = "timetopractice"; string p = "toc"; cout << minWindow(s, p); // 输出：toprac return 0; }

2. Java

class DSA { // 最优解法：滑动窗口（双指针） // 时间复杂度 O(n)，空间复杂度 O(1) public static String minWindow(String s, String p) { int len1 = s.length(); int len2 = p.length(); // 如果 s 比 p 短，直接返回空字符串 if (len1 < len2) return ""; int[] countP = new int[256]; // 存储模式串 p 的字符频次 int[] countS = new int[256]; // 存储当前窗口的字符频次 // 统计 p 中所有字符的出现次数 for (int i = 0; i < len2; i++) countP[p.charAt(i)]++; int start = 0; // 窗口左指针 int start_idx = -1; // 最小窗口的起始索引 int min_len = Integer.MAX_VALUE; // 最小窗口长度 int matchCount = 0; // 已匹配字符数 // 右指针 j 向右扩展窗口 for (int j = 0; j < len1; j++) { char currChar = s.charAt(j); // 将当前字符加入窗口 countS[currChar]++; // 如果当前字符是 p 需要的，且数量未超过，计数+1 if (countP[currChar] > 0 && countS[currChar] <= countP[currChar]) { matchCount++; } // ======================== // 窗口已包含 p 所有字符 → 收缩左指针，最小化窗口 // ======================== if (matchCount == len2) { char startChar; // 尝试缩小窗口：移除多余字符 while (countS[startChar = s.charAt(start)] > countP[startChar] || countP[startChar] == 0) { if (countS[startChar] > countP[startChar]) { countS[startChar]--; } start++; } // 更新最小窗口 int currWindowLen = j - start + 1; if (min_len > currWindowLen) { min_len = currWindowLen; start_idx = start; } } } // 未找到有效窗口 if (start_idx == -1) return ""; // 截取并返回最小窗口 return s.substring(start_idx, start_idx + min_len); } // 测试主函数 public static void main(String[] args) { String s = "timetopractice"; String p = "toc"; String res = minWindow(s, p); System.out.println(res); // 输出：toprac } }

3. Python

def minWindow(s, p): len1 = len(s) len2 = len(p) # 如果 s 比 p 短，直接返回空 if len1 < len2: return "" countP = [0] * 256 # 统计 p 中字符频次 countS = [0] * 256 # 统计当前窗口字符频次 # 记录模式串 p 中每个字符的出现次数 for char in p: countP[ord(char)] += 1 start = 0 # 窗口左指针 start_idx = -1 # 最小窗口起始位置 min_len = float('inf')# 最小窗口长度 match_count = 0 # 已匹配的字符数量 # 右指针 j 扩展窗口 for j in range(len1): # 当前字符加入窗口 countS[ord(s[j])] += 1 # 如果当前字符是 p 需要的，且数量没超，有效匹配 +1 if countP[ord(s[j])] != 0 and countS[ord(s[j])] <= countP[ord(s[j])]: match_count += 1 # ======================== # 窗口已包含所有 p 字符 → 收缩左指针，最小化窗口 # ======================== if match_count == len2: # 尝试缩小窗口：移除多余的、不需要的字符 while countS[ord(s[start])] > countP[ord(s[start])] or countP[ord(s[start])] == 0: if countS[ord(s[start])] > countP[ord(s[start])]: countS[ord(s[start])] -= 1 start += 1 # 更新最小窗口 curr_len = j - start + 1 if min_len > curr_len: min_len = curr_len start_idx = start # 没找到有效窗口 if start_idx == -1: return "-1" # 返回最小窗口子串 return s[start_idx:start_idx + min_len] # 测试 s = "timetopractice" p = "toc" res = minWindow(s, p) print(res) # 输出：toprac

4. C#

using System; class DSA { // 最优解法：滑动窗口（双指针） // 时间复杂度 O(n)，空间复杂度 O(1) public static string minWindow(string s, string p) { int len1 = s.Length; int len2 = p.Length; // 如果 s 比 p 短，直接返回空 if (len1 < len2) return ""; int[] countP = new int[256]; // 存储 p 的字符频次 int[] countS = new int[256]; // 存储当前窗口的字符频次 // 统计模式串 p 中所有字符的出现次数 for (int i = 0; i < len2; i++) countP[p[i]]++; int start = 0; // 窗口左指针 int start_idx = -1; // 最小窗口起始位置 int min_len = int.MaxValue; // 最小窗口长度 int matchCount = 0; // 已匹配字符数量 // 右指针 j 向右扩展窗口 for (int j = 0; j < len1; j++) { char currChar = s[j]; // 当前字符加入窗口 countS[currChar]++; // 如果字符是 p 需要的，且数量未超标 → 有效匹配+1 if (countP[currChar] > 0 && countS[currChar] <= countP[currChar]) { matchCount++; } // ======================== // 窗口已包含所有 p 字符 → 收缩左指针，最小化窗口 // ======================== if (matchCount == len2) { char startChar; // 尝试缩小窗口：移除多余/无用字符 while (countS[startChar = s[start]] > countP[startChar] || countP[startChar] == 0) { if (countS[startChar] > countP[startChar]) countS[startChar]--; start++; } // 更新最小窗口 int currLen = j - start + 1; if (min_len > currLen) { min_len = currLen; start_idx = start; } } } // 未找到有效窗口 if (start_idx == -1) return ""; // 返回最小窗口子串 return s.Substring(start_idx, min_len); } // 测试主函数 public static void Main(string[] args) { string s = "timetopractice"; string p = "toc"; string res = minWindow(s, p); Console.WriteLine(res); // 输出：toprac } }

5. JavaScript

function minWindow(s, p) { let len1 = s.length; let len2 = p.length; // s 比 p 短，直接返回空 if (len1 < len2) { return ""; } let countP = new Array(256).fill(0); // 统计 p 字符频次 let countS = new Array(256).fill(0); // 统计窗口字符频次 // 统计模式串 p 的字符出现次数 for (let char of p) { countP[char.charCodeAt(0)]++; } let start = 0; // 左指针 let startIdx = -1; // 最小窗口起点 let minLen = Infinity; // 最小窗口长度 let count = 0; // 已匹配字符数 // 右指针 j 扩展窗口 for (let j = 0; j < len1; j++) { let code = s[j].charCodeAt(0); // ✅ 修复：统一获取字符编码 countS[code]++; // 有效匹配字符计数 if (countP[code] !== 0 && countS[code] <= countP[code]) { count++; } // 窗口已包含所有 p 字符 → 收缩左指针 if (count === len2) { let startCode = s[start].charCodeAt(0); while (countS[startCode] > countP[startCode] || countP[startCode] === 0) { if (countS[startCode] > countP[startCode]) { countS[startCode]--; } start++; startCode = s[start].charCodeAt(0); } // 更新最小窗口 let length = j - start + 1; if (minLen > length) { minLen = length; startIdx = start; } } } return startIdx === -1 ? "" : s.substring(startIdx, startIdx + minLen); } // 测试 let s = "timetopractice"; let p = "toc"; let result = minWindow(s, p); console.log(result);

(三)代码输出和算法复杂度

输出：

toprac

时间复杂度：O(n)

空间复杂度：O(1)