C++刷leetcode（76. 最小覆盖子串）【滑动窗口】
题目描述：给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
string minWindow(string s, string t) {
map<char, int> need, store;
for(auto cha : t)need++;
int left = 0, right = 0;
int start = 0, valid = 0;
int len = INT_MAX;
while(right < s.size()){
char temp = s;
right++;
if(need.count(temp) != 0){
store++;
if(store == need)valid++;
}
while(valid == need.size()){//注意此处的判断
if(right - left < len){
len = right - left;
start = left;
}
char temp1 = s;
left++;
if(need.count(temp1)!=0){
if(need == store)valid--;
store--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
参考链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/ 相似题目：面试题 17.18. 最短超串
题目描述：
假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 1:
输入:
big =
small =
输出:
示例 2:
输入:
big =
small =
输出: []
提示：
big.length <= 100000
1 <= small.length <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-supersequence-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
map<int, int> need, store;
for(auto cha : small)need++;
int left = 0, right = 0;
int start = 0, valid = 0;
int len = INT_MAX;
//先固定右端再逐渐缩短左端
while(right < big.size()){
int temp = big;
right++;
if(need.count(temp) != 0){
store++;
if(store == need)valid++;
}
while(valid == need.size()){
if(right - left < len){
len = right - left;
start = left;
}
int temp1 = big;
left++;
if(need.count(temp1)!=0){
if(need == store)valid--;
store--;
}
}
}
vector<int>res;
if(len != INT_MAX)res = {start, start + len - 1};
return res;
}
};
页:
[1]