经典面试题之滑动窗口专题
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 长度最小的子数组 // 大于等于 targetint min_len = INT32_MAX;// 总和int sum = 0;int start = 0; // 起点for(int i = 0; i< nums.size(); i++) {sum += nums[i];while(sum >= target) {int len = i-start+1;if(len < min_len ) {min_len = len;} sum -= nums[start++];} }if(min_len == INT32_MAX ) {return 0; } else {return min_len;}}
};
3. 无重复字符的最长子串
class Solution {
public:int lengthOfLongestSubstring(string s) {// 长度int str_size = s.size();if(str_size == 0) {return 0;}int max_len = 0;int left = 0;unordered_set<char> str; // 用来存储 字符for(int i = 0; i< str_size ; i++ ){// 如果没有找到 该字符while(str.find(s[i]) != str.end()) {str.erase(s[left]);left++;}max_len = max(max_len, i- left + 1);// 插入str.insert(s[i]);}return max_len;}
};
76 最小覆盖子串
class Solution {
public:unordered_map<char,int> tstr, sstr;bool check() {for(auto tchar : tstr) {if(tchar.second > sstr[tchar.first]) {return false;}}return true;}string minWindow(string s, string t) {int n1 = s.size();int n2 = t.size();if(n1 < n2) return "";int len = INT_MAX;int ans_left = -1; // 最小窗口的左边界// 构建哈希表for(auto tchar : t) {tstr[tchar]++;}int left = 0;int right= 0;for(int right = 0; right < n1; right++) {sstr[s[right]]++; // 添加// 说明找到 该字符if(tstr.find(s[right]) != tstr.end()) {// 这里是对比一下 sstr 以及 tstr while(check() && left <= right) {// 长度变化if(len > right-left +1) {// 标记 左边界ans_left = left;len = right - left + 1; }// 去掉sstr[s[left]]--;// 左边界移动left++;}}}if(ans_left == -1) return "";else return s.substr(ans_left, len);}
};
收获
- unordered_map 的基本使用
- 滑动窗口模版
- auto 基本使用
定义一个字符串的个数哈希表
unordered_map<char, int> sstr, tstr;
简单访问
sstr[s[i]] 这个访问就是对应的个数
int main() {unordered_map<char, int> myMap;unordered_map<char, int> myMap2;myMap['a'] = 1;myMap['b'] = 2;myMap['c'] = 3;myMap2['a'] = 3;myMap2['b'] = 1;myMap2['c'] = 2;// 打印 unordered_map 中的元素for (auto pair : myMap) {cout << pair.first << ": " << pair.second << endl;cout<<myMap2[pair.first]<<endl;cout<<myMap[pair.first]<<endl;}
}