leetcode76.最小覆盖子串

题目如下

数据范围

首先本题可以利用不定长的滑动窗口思想不断枚举右端同时检查窗口是否符合题意。 但是这样做每次新枚举一个窗口都要检查造成了很多重复计算。 我们发现其实每次变化要么是少一个字符要么是多一个字符而中间的根本没变。 所以，我们令字符串t出现的字符种类为m， 在枚举右端点的过程中每当窗口内的某个字符出现频率增加到与字符串t一样时count++。 在m == count时我们会发现此时答案可能出现在窗口内， 所以我们不断移动左端点同时减少对应的字符的频数当这个频数小于t中的频数时显然我们不能移动左端点了。 在这个过程中不断得到最小长度以及子串起始地址然后返回即可。

未优化通过代码

class Solution { public: bool check() { for (auto& p : mapt) { if (maps[p.first] < p.second) return false; } return true; } unordered_map<char, int> mapt, maps; string minWindow(string s, string t) { int n = s.size(); int m = t.size(); if (m > n) return ""; for (char c : t) mapt[c]++; int l = 0, r = 0; int ans = INT_MAX; int st = 0; while (r <= n) { if (mapt.count(s[r])) { maps[s[r]]++; } r++; while (l <= r && check()) { if (r - l < ans) { ans = r - l; st = l; } if (mapt.count(s[l])) { maps[s[l]]--; } l++; } } return ans == INT_MAX ? "" : s.substr(st, ans); } };

优化后的通过代码

class Solution { public: bool check() { for (auto& p : mapt) { if (maps[p.first] < p.second) return false; } return true; } unordered_map<char, int> mapt, maps; string minWindow(string s, string t) { int n = s.size(); int m = t.size(); if (m > n) return ""; int count = 0; for (char c : t) mapt[c]++; m = mapt.size(); int l = 0, r = 0; int ans = INT_MAX; int st = 0; while (r <= n) { if (mapt.count(s[r])) { maps[s[r]]++; // cout << maps[s[r]] << endl; if (maps[s[r]] == mapt[s[r]]) { count++; } while (l <= r && count == m) { // cout << r << endl; if (r - l + 1 < ans) { ans = r - l + 1; st = l; } if (mapt.count(s[l])) { maps[s[l]]--; if (maps[s[l]] < mapt[s[l]]) { l++; count--; break; } } l++; } } r++; } // cout << ans; return ans == INT_MAX ? "" : s.substr(st, ans); } };