Leetcode 刷题记录 03 —— 滑动窗口
本系列为笔者的 Leetcode 刷题记录,顺序为 Hot 100 题官方顺序,根据标签命名,记录笔者总结的做题思路,附部分代码解释和疑问解答。
目录
01 无重复字符的最长子串
方法:滑动窗口
02 找到字符串中所有字母异位词
方法一:滑动窗口
方法二:滑动窗口Plus
01 无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
}
};
方法:滑动窗口
-
建立左指针
lk
和右指针rk
-
lk
指向滑动窗口第一个元素 -
rk
指向滑动窗口最后一个元素 -
不断地去掉第一个元素,添加最后一个元素,判断
!occ.count(s[rk+1])
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> occ;
int n = s.size();
int rk = -1; //右指针
int ans = 0;
for(int lk=0; lk<n; ++lk){ //左指针
if(lk != 0) occ.erase(s[lk-1]);
while(rk+1 < n && !occ.count(s[rk+1])){
occ.insert(s[rk+1]);
++rk;
}
ans = max(ans, rk-lk+1);
}
return ans;
}
};
02 找到字符串中所有字母异位词
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
}
};
方法一:滑动窗口
-
建立两个数组
sCount(26)
和pCount(26)
-
sCount(26)
记录s
中的字母情况 -
pCount(26)
记录p
中的字母情况 -
不断地去掉第一个元素,添加最后一个元素,判断
sCount == pCount
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;
}
};
方法二:滑动窗口Plus
-
建立一个数组
count(26)
-
count(26)
记录s
和p
差异情况 -
不断地去掉第一个元素,添加最后一个元素,判断
differ == 0
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> count(26);
int differ = 0;
for(int i=0; i<pLen; ++i){
++count[s[i] - 'a'];
--count[p[i] - 'a'];
}
for(int j=0; j<26; j++){
if(count[j]) ++differ;
}
if(differ == 0) ans.emplace_back(0);
for(int i=0; i<(sLen - pLen); ++i){
if(count[s[i] - 'a'] == 0) ++differ;
else if(count[s[i] - 'a'] == 1) --differ;
--count[s[i] - 'a'];
if(count[s[i + pLen] - 'a'] == 0) ++differ;
else if(count[s[i + pLen] - 'a'] == -1) --differ;
++count[s[i + pLen] - 'a'];
if(differ == 0) ans.emplace_back(i + 1);
}
return ans;
}
};
文章部分代码来源于力扣(LeetCode)