LeetCode热题100（滑动窗口篇）
题目出自Leetcode热题100：Leetcode热题100
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
思路
这种子串子数组问题，而且还满足窗口的右边界右移动就是加，左边界右移就是减的问题大概率就是滑动窗口。
[]即为窗口
确认完滑动窗口后最关键的就是，移动左窗口的条件。以这题，题目的目的为无重复字符的最长子串，那么移动左窗口的条件就是子串中出现了重复字符，只要出现的重复字符就向右移动窗口，直到窗口中的字符重新满足条件。
那么新的问题出现了，如何判断窗口中是否存在重复字符——哈希表，哈希表可以快速判断是否存在重复字符，只要把窗口中的数字存入到哈希表中即可。当左窗口移动时把离开窗口的字符从哈希表中取出。
代码
C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0,n = s.size();
unordered_map<char,int> cnt;
for(int l = 0,r = 0;r<n;++r)
{
//if(cnt.find(s[r])==cnt.end())
cnt[s[r]] += 1;
while(cnt[s[r]]>1)
{
if(cnt[s[l]] == 1)
{
cnt.erase(s[l]);
}
else
{
cnt[s[l]]-=1;
}
l++;
}
ans = max(ans,(int)cnt.size());
}
return ans;
}
};
Java
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character,Integer> cnt = new HashMap<>();
int ans = 0,n = s.length();
for(int l = 0,r = 0;r<n;++r){
//cnt.put(s.get(r),cnt.getOrDefault(s.get(r),0)+1);
cnt.merge(s.charAt(r),1,Integer::sum);
while(cnt.get(s.charAt(r))>1){
if(cnt.get(s.charAt(l))>1){
cnt.merge(s.charAt(l),-1,Integer::sum);
}
else{
cnt.remove(s.charAt(l));
}
l++;
}
ans = Math.max(ans,cnt.size());
}
return ans;
}
}
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
l = 0
r = 0
cnt = defaultdict(int)
while r<len(s):
cnt[s[r]]+=1
while cnt[s[r]]>1:
if(cnt[s[l]] == 1):
cnt.pop(s[l])
else:
cnt[s[l]]-=1
l+=1
ans = max(ans,len(cnt))
r+=1
return ans
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
思路
这种子串子数组问题，而且还满足窗口的右边界右移动就是加，左边界右移就是减的问题大概率就是滑动窗口。
[cba]ebabacd
[]即为窗口
确认完滑动窗口后最关键的就是，移动左窗口的条件。以这题，题目的目的为找到字符串中所有字母异位词，那么移动左窗口的条件就是子串的长度大于p的长度，只要出现子串的长度大于p的长度就向右移动窗口，直到窗口中的字符重新满足条件。
那么新的问题出现了，如何判断窗口中是否存在字符串中所有字母异位词——哈希表，哈希表可以快速判断是否存在所有字母异位词，只要有两个哈希表，一个哈希表存储p的字符，另一个哈希表存储窗口内的字符，右窗口遍历过程中只要把窗口中的数字存入到哈希表中即可。当左窗口移动时把离开窗口的字符从哈希表中取出。
最后只要两个哈希表相同就可以记录坐标了。
代码
C++
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size();
vector<int> ans;
unordered_map<char,int> cnt;
unordered_map<char,int> mp;
for(char ch:p)
{
cnt[ch]+=1;
}
for(int l = 0,r = 0;r<n;++r)
{
mp[s[r]]+=1;
while(r-l+1>p.size())
{
if(mp[s[l]] == 1) mp.erase(s[l]);
else mp[s[l]]-=1;
l++;
}
if(cnt == mp)
ans.push_back(l);
}
return ans;
}
};
Java
class Solution {
public boolean check(HashMap<Character,Integer>cnt,HashMap<Character,Integer>mp){
for(Map.Entry<Character,Integer> entry:mp.entrySet()){
if(!cnt.containsKey(entry.getKey())||cnt.containsKey(entry.getKey())&&cnt.get(entry.getKey()) != entry.getValue())
return false;
}
return true;
}
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character,Integer> cnt = new HashMap<>();
HashMap<Character,Integer> mp = new HashMap<>();
List<Integer> ans = new ArrayList<>();
for(char ch:p.toCharArray()){
cnt.merge(ch,1,Integer::sum);
}
int n = s.length();
for(int l = 0,r = 0;r<n;++r){
mp.merge(s.charAt(r),1,Integer::sum);
while(r-l+1>p.length()){
if(mp.get(s.charAt(l))>1){
mp.merge(s.charAt(l),-1,Integer::sum);
}
else{
mp.remove(s.charAt(l));
}
l++;
}
if(cnt.equals(mp)){
ans.add(l);
}
}
return ans;
}
}
Python
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
cnt = {}
mp = {}
for ch in p:
cnt[ch] = cnt.get(ch,0)+1
l,r = 0,0
while r<len(s):
mp[s[r]] = mp.get(s[r],0)+1
while r-l+1>len(p):
if(mp[s[l]] == 1):
mp.pop(s[l])
else:
mp[s[l]]-=1
l+=1
if cnt == mp:
ans.append(l)
r+=1
return ans
总结
滑动窗口主要是针对那种子数组和子串问题，在满足子数组和子串后还有一个条件就是单调性。也就是右窗口移动导致窗口内的有效内容增加，左窗口移动导致窗口内有效内容减少。
此篇章记录我的刷图历程
原文地址：https://blog.csdn.net/2303_79015671/article/details/145192738
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！