LeetCode 滑动窗口专题

曾经终败给现在 2023-01-18 09:26 25阅读 0赞

[3. 无重复字符的最长子串][3.]

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

> 输入: s = “abcabcbb”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

> 输入: s = “bbbbb”  
> 输出: 1  
> 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

> 输入: s = “pwwkew”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。  
> 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

*  动态规划

class Solution {
        
    public:
        int lengthOfLongestSubstring(string s) {
        
            // 动态规划 dp[i]: 以字符s[i]为结尾的最长不重复子串“长度”
            // if i - j > dp[i-1] ---> dp[i] = dp[i-1] + 1
            // if i - j <= dp[i-1] ---> dp[i] = i - j
            if(s.length() == 0) return 0;
            vector<int> dp(s.length(),0);
            dp[0] = 1;
            int res = 1;
            for(int i=1; i<s.length(); ++i){
        
                int j = i-1;
                for(; j>=0; --j){
        
                    if(s[j] == s[i]){
        
                        break;
                    }
                }
                if(i - j > dp[i-1]){
        
                    dp[i] = dp[i-1]+1;
                }else{
        
                    dp[i] = i-j;
                }
                res = max(dp[i], res);
            } 
            return res;
        }
    };

*  滑动窗口

class Solution {
        
    public:
        int lengthOfLongestSubstring(string s) {
        
            // 滑动窗口 
            // 对于 s = "abcabcbb"， 如果滑动窗口为"abc"则满足，但是滑动到下一个a，发现不满足，所以要移出去之前的a。
            if(s.length() == 0) return 0;
            int res = 1;
            unordered_set<int> lookup;
            int l = 0;
            for(int i=0; i<s.length(); ++i){
        
                while(lookup.find(s[i]) != lookup.end()){
        
                    lookup.erase(s[l++]);
                }
                res = max(res, i-l+1);
                lookup.insert(s[i]);
            }
            return res;
        }
    };

[30. 串联所有单词的子串  
][30. _]

[76. 最小覆盖子串][76.]

[159. 至多包含两个不同字符的最长子串][159.]

[209. 长度最小的子数组  
][209. _]

[239. 滑动窗口最大值][239.]

[567. 字符串的排列][567.]

[727. 最小窗口子序列][727.]

[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[30. _]: https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
[76.]: https://leetcode-cn.com/problems/minimum-window-substring/
[159.]: https://leetcode-cn.com/problems/longest-substring-with-at-most-two-distinct-characters/
[209. _]: https://leetcode-cn.com/problems/minimum-size-subarray-sum/
[239.]: https://leetcode-cn.com/problems/sliding-window-maximum/
[567.]: https://leetcode-cn.com/problems/permutation-in-string/
[727.]: https://leetcode-cn.com/problems/minimum-window-subsequence/