C++刷leetcode（76. 最小覆盖子串）【滑动窗口】

糖逗

题目描述：

1. 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
   
2. 
   
3. 示例：
   
4. 
   
5. 输入: S = "ADOBECODEBANC", T = "ABC"
   
6. 输出: "BANC"
   
7. 说明：
   
8. 
   
9. 如果 S 中不存这样的子串，则返回空字符串 ""。
   
10. 如果 S 中存在这样的子串，我们保证它是唯一的答案。
    
11. 
    
12. 来源：力扣（LeetCode）
    
13. 链接：https://leetcode-cn.com/problems/minimum-window-substring
    
14. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     string minWindow(string s, string t) {
   
4.         map<char, int> need, store;
   
5.         for(auto cha : t)need[cha]++;
   
6. 
   
7.         int left = 0, right = 0;
   
8.         int start = 0, valid = 0;
   
9.         int len = INT_MAX;
   
10.         while(right < s.size()){
    
11.             char temp = s[right];
    
12.             right++;
    
13. 
    
14.             if(need.count(temp) != 0){
    
15.                 store[temp]++;
    
16.                 if(store[temp] == need[temp])valid++;
    
17.             }
    
18. 
    
19.             while(valid == need.size()){//注意此处的判断
    
20.                 if(right - left < len){
    
21.                     len = right - left;
    
22.                     start = left;
    
23.                 }
    
24.                 char temp1 = s[left];
    
25.                 left++;
    
26.                 if(need.count(temp1)!=0){
    
27.                     if(need[temp1] == store[temp1])valid--;
    
28.                     store[temp1]--;
    
29.                 }
    
30.             }
    
31.         }
    
32.         return len == INT_MAX ? "" : s.substr(start, len);
    
33.     }
    
34. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -yong-si-xiang-by-/

糖逗

相似题目：面试题 17.18. 最短超串
题目描述：

1. 假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
   
2. 
   
3. 返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入:
   
8. big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
   
9. small = [1,5,9]
   
10. 输出: [7,10]
    
11. 示例 2:
    
12. 
    
13. 输入:
    
14. big = [1,2,3]
    
15. small = [4]
    
16. 输出: []
    
17. 提示：
    
18. 
    
19. big.length&#160;<= 100000
    
20. 1 <= small.length&#160;<= 100000
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/shortest-supersequence-lcci
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
   
4.         map<int, int> need, store;
   
5.         for(auto cha : small)need[cha]++;
   
6. 
   
7.         int left = 0, right = 0;
   
8.         int start = 0, valid = 0;
   
9.         int len = INT_MAX;
   
10.         //先固定右端再逐渐缩短左端
    
11.         while(right < big.size()){
    
12.             int temp = big[right];
    
13.             right++;
    
14.             if(need.count(temp) != 0){
    
15.                 store[temp]++;
    
16.                 if(store[temp] == need[temp])valid++;
    
17.             }
    
18. 
    
19.             while(valid == need.size()){
    
20.                 if(right - left < len){
    
21.                     len = right - left;
    
22.                     start = left;
    
23.                 }
    
24. 
    
25.                 int temp1 = big[left];
    
26.                 left++;
    
27.                 if(need.count(temp1)!=0){
    
28.                     if(need[temp1] == store[temp1])valid--;
    
29.                     store[temp1]--;
    
30.                 }
    
31.             }
    
32.         }
    
33.         vector<int>res;
    
34.         if(len != INT_MAX)res = {start, start + len - 1};
    
35.         return res;
    
36.     }
    
37. };

复制代码