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 = 0l = 0r = 0cnt = defaultdict(int)while r<len(s):cnt[s[r]]+=1while cnt[s[r]]>1:if(cnt[s[l]] == 1):cnt.pop(s[l])else:cnt[s[l]]-=1l+=1ans = max(ans,len(cnt))r+=1return 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)+1l,r = 0,0while r<len(s):mp[s[r]] = mp.get(s[r],0)+1while r-l+1>len(p):if(mp[s[l]] == 1):mp.pop(s[l])else:mp[s[l]]-=1l+=1if cnt == mp:ans.append(l)r+=1return ans

总结

滑动窗口主要是针对那种子数组和子串问题，在满足子数组和子串后还有一个条件就是单调性。也就是右窗口移动导致窗口内的有效内容增加，左窗口移动导致窗口内有效内容减少。
此篇章记录我的刷图历程