76.最小覆盖子串
思路:
双指针滑动窗口问题,指针的移动条件是双指针的核心。
反思:
1、考虑右指针已经移动到最右端,无法继续移动的情况。(flag1的思路)
2、用map.empty()是要千万注意:map[key]相当于往map中添加元素
代码:
class Solution { public: unordered_map<char, int> mp; bool empty(){ for(auto it = mp.begin(); it != mp.end(); it++){ if(it -> second > 0) return false; } return true; } string minWindow(string s, string t) { vector<vector<int>> ans; int index[100005]={0}; for(int i = 0; i < t.size(); i++){ mp[t[i]]++; } int pre = -1, start = -1; for(int i = 0; i < s.size(); i++){ if(mp[s[i]]){ if(pre == -1) start = i; if(pre != -1) index[pre] = i; pre = i; } } if(start == -1){ return ""; } int l = start, r = start; bool flag1 = true; while(l <= r){ while(!empty() && flag1){ mp[s[r]]--; if(index[r] == 0){ flag1 = false; break; } if(!empty())r = index[r]; } // cout<<l<<" "<<r<<" "<<mp['a']<<" "<<mp['e']<<" "<<mp['c']<<endl; if(empty()){ ans.push_back({l, r}); mp[s[l]]++; if(index[l] == 0) break; l = index[l]; }else{ break; } if(!empty() && index[r] != 0){ r = index[r]; } } int minn = 100005, minl = -1 , minr = -1; for(int i = 0; i < ans.size(); i++){ int rr = ans[i][1], ll = ans[i][0]; if(rr - ll < minn){ minn = rr - ll; minl = ll; minr = rr; } } if(minl == -1){ return ""; }else{ return s.substr(minl, minr - minl + 1); } } };
标签:子串,pre,start,int,76,map,mp,指针 From: https://www.cnblogs.com/yccy/p/18114451