共计 1176 个字符，预计需要花费 3 分钟才能阅读完成。
leetcode 76. 最小笼罩子串
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”。
留神：
对于 t 中反复字符，咱们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，咱们保障它是惟一的答案。示例 1：
输出：s = “ADOBECODEBANC”, t = “ABC”
输入：”BANC”
应用两个哈希表，ht 存字符串 t 的字符呈现次数。而后遍历字符串 s，当某个字符次数还未到 t 中的次数，则示意该字符是无效字符[可用于笼罩 t]。
双指针算加须要指针具备枯燥性，这样工夫复杂度能力为 O(n)。
枯燥性证实：假如 [j, i] 之间的字符为涵盖 t 的一段，则当 i 往后走到 i ’，[j, i’]必定也涵盖了 t。此时 j 也只能往后走，因为要求的是最小子串。
什么时候 j 能够往后走：当 s[j]呈现次数 大于 t 中的次数时，阐明即便没有 s[j]，[j, i] 中也至多有了 ht[s[j]]个 s[j]了，故此时曾经不须要 j 地位字符。
unordered_map<char, int> hs, ht;
string minWindow(string s, string t) {for (char c : t) ht++;
string ans;
for (int i = 0, j = 0, cnt = 0; i < s.size(); i++) {hs[s[i]]++;
if (hs[s[i]] <= ht[s[i]]) cnt++;
while (hs[s[j]] > ht[s[j]]) // 不能是 >=，因为只有当该字符在 hs 中冗余了，能力将该字符略过
hs[s[j++]]--;
if (cnt == t.size()) {if (ans.empty() || i - j + 1 < ans.size())
ans = s.substr(j, i - j + 1);
}
}
return ans;
}leetcode 3. 无反复字符的最长子串
给定一个字符串 s，请你找出其中不含有反复字符的 最长子串 的长度。
示例 1:
输出: s = “abcabcbb”
输入: 3
解释: 因为无反复字符的最长子串是 “abc”，所以其长度为 3。
指针枯燥性证实 [反证]：假如[j, i] 为以后无反复字符最长子串，则当 i 向后走到 i ’ 时，如果此时 j 往前走，[j’, i]必定蕴含反复字符，不符题意。故当 i 往后，j 也只能往后走。
什么时候 j 能够往后走：当新加进来的 i 字符反复了，此时就须要让 j 往后走，直到 [j, i] 无反复字符。
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hmap;
int ans = 0;
for (int i = 0, j = 0; i < s.size(); i++) {hmap[s[i]]++;
while (hmap[s[i]] > 1) hmap[s[j++]]--;
ans = max(ans, i - j + 1);
}
return ans;
}
