「LeetCode Top100」之滑动窗口
3. 无重复字符的最长子串
题目链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
题目难度:中等
标签:哈希表
、字符串
、滑动窗口
题目状态:学习题解
思路:
滑动窗口的思路,也就是维持一个无序队列unordered_set<char>
用来当作这个窗口。
- 遍历字符串,若当前字符不在窗口中,就将该字符
insert
进窗口中,然后将长度加1。 - 若当前字符在窗口中,就将窗口的左侧元素移除,这样就实现了移动这个窗口。然后判断当前的子串长度是否大于之前的长度。
当遍历结束,就获得了子串的最大长度。
代码:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
unordered_set<char> window;
int maxStr = 0;
int left = 0;
for(int i = 0; i < s.size(); ++i) {
while(window.find(s[i]) != window.end()) {
window.erase(s[left]);
left++;
}
maxStr = max(maxStr, i - left + 1);
window.insert(s[i]);
}
return maxStr;
}
};
438. 找到字符串中所有字母异位词
题目链接:https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
题目难度:中等
标签:哈希表
、字符串
、滑动窗口
题目状态:学习题解
思路:
这题使用滑动窗口解决,滑动窗口的大小是p的大小。然后创建两个26位的数组,pCount和sCount,其中pCount保存p的字母状态,这个是固定的,用来与sCount进行比较的。sCount中保存的是当前滑动窗口里面的s的字母状态。若pCount和sCount相等,则压入结果数组中。
代码:
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if(sLen < pLen) return vector<int>();
vector<int> ans;
vector<int> sCount(26);
vector<int> pCount(26);
for(int i = 0; i < pLen; ++i) {
++sCount[s[i] - 'a'];
++pCount[p[i] - 'a'];
}
if(sCount == pCount) ans.emplace_back(0);
for(int i = 0; i < sLen - pLen; ++i) {
--sCount[s[i] - 'a'];
++sCount[s[i + pLen] - 'a'];
if(sCount == pCount) ans.emplace_back(i + 1);
}
return ans;
}
};
热门相关:我会一直喜欢你 完美隐婚,律师老公不太坏 兵王无双 完美隐婚 超能狂兵