【LeetCode】数组问题：滑动窗口

深碍√TFBOYSˉ_ 2022-10-29 09:11 148阅读 0赞

### 滑动窗口 ###

*  对于数组中要选一个连续的序列，那势必就是滑动窗口；
    
     *  动态规划适用于选择非连续的序列
 *  和快慢指针的区别是，快指针每次循环必定加一，而滑动窗口是 r 或者 l 指针其中一个加一

策略

*  对于求最小窗口
    
     *  到满足条件时，r（前面的指针）不再 ++；之后 l（后面的指针 ）++，把窗口变得又不满足条件
 *  对于最大窗口
    
     *  一直 r++，直到不满足条件再让 l++
 *  对于窗口的最值是每次循环时用 max|min（res ，r - l (+ 1)）计算。

结题结构

int r = -1 , l = 0;
    
    while(r < length){ 
        if(不满足条件){ 
            r ++;
            // 处理 ....（注意跳过 r == length 时的情况）
        }else { 
            l ++;
             // 处理 ....
        }
        
        // 处理 ....（注意跳过 r == length 时的情况）
    }

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

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]
    输出：2
    解释：子数组 [4,3] 是该条件下的长度最小的子数组。

**题解**

动态规划：不行，空间超了

class Solution { 
        public int minSubArrayLen(int s, int[] nums) { 
            int[][] dp = new int[nums.length + 1][s + 1];
    
            for(int i = nums.length - 1 ; i >= 0  ; i --){ 
                for(int j = 1 ; j <= s ; j ++){ 
                    if( nums[i] >= j){ 
                        dp[i][j] = 1;
                    }else { 
                        dp[i][j] = dp[i + 1][j - nums[i]] == 0 ? 0 : dp[i + 1][j - nums[i]] + 1;
                    }
                }
            }
    
            int res =  Integer.MAX_VALUE;
            for(int i = 0 ; i < nums.length ; i ++){ 
                if(dp[i][s] != 0){ 
                    res = Math.min(res , dp[i][s]);
                }
            }
    
            return res ==  Integer.MAX_VALUE ? 0 : res;
        }
    }

滑动窗口

class Solution { 
        public int minSubArrayLen(int s, int[] nums) { 
            int l = 0 , r = -1 , sum = 0;
            int res = Integer.MAX_VALUE;
            
            while(r < nums.length){ 
                if(sum < s){ 
                    sum += (r + 1 < nums.length) ? nums[r + 1] : 0 ;
                    r ++;
                }else { 
                    sum -= nums[l++];
                }
    
                if(sum >= s){ 
                    res = Math.min(res , r - l + 1);
                }
            }
    
            return res == Integer.MAX_VALUE ? 0 : res ;
        }
    }

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: s = ""
    输出: 0

**题解**

class Solution {
        public int lengthOfLongestSubstring(String s) {
            char[] windowsIdx = new char[s.length()];
            int l = 0 ,  r = 0;
            int res = 0;
    
            while( r < s.length()){
                windowsIdx[r - l] = s.charAt(r ++);
    
                if(r == s.length()){
                    res = Math.max(res , r - l);
                    break;
                }
    
                for(int i = 0 ; i <= r - l - 1  && r < s.length(); i ++){
                    if(s.charAt(r) == windowsIdx[i]){
                        res = Math.max(res , r - l);
                        r = l = l + 1;
                        break;
                    }
                }
            }
    
            return res ;
        }
    }

#### [438. 找到字符串中所有字母异位词][438.] ####

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。  
不考虑答案输出的顺序。

示例 1:

输入:
    s: "cbaebabacd" p: "abc"
    
    输出:
    [0, 6]
    
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:
    s: "abab" p: "ab"
    
    输出:
    [0, 1, 2]
    
    解释:
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

**暴力**

*  关键是查找那里，不能再嵌套遍历，改为数组索引
 *  **但凡是要检查一个字符是否出现过，一定是查找表**

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            int[] pTable = new int[26];
    
            for(int i = 0 ; i < s.length() - p.length() + 1 ; i ++){
                initPTable(p , pTable);
    
                for(int j = 0 ; j < p.length() ; j ++){
                    pTable[s.charAt(i + j) - 'a'] --;
                }
    
                boolean isTrue = true;
                for(int j = 0 ; j < pTable.length ; j ++){
                    if(pTable[j] != 0){
                        isTrue = false;
                    }
                }
    
                if(isTrue)  res.add(i);
            }
    
            return res;
        }
    
        void initPTable(String p , int[] pTable){
            for(int i = 0 ; i < pTable.length ; i ++){
                pTable[i] = 0;
            }
            for(int i = 0 ; i < p.length() ; i ++){
                pTable[p.charAt(i) - 'a'] ++;
            }
        }
    }

**滑动窗口**

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            int r = -1 , l = 0;
            int[] pTable = new int[26];
    
            while( r < s.length()){
                if( r - l + 1 < p.length()){
                    r ++;
                }else{
                    l ++;
                }
    
                if(r != s.length() && r - l + 1 == p.length()){
                    initPTable(p , pTable);
    
                    for(int i = l ; i <= r; i ++ ){
                        pTable[s.charAt(i) - 'a'] --;
                    }
    
                    boolean isMatch = true;
                    for(int i = 0 ; i < pTable.length ; i++){
                        if(pTable[i] != 0){
                            isMatch = false;
                        }
                    }
    
                    if(isMatch) res.add(l);
                }
            }
    
            return res;
        }
    
        void initPTable(String p , int[] pTable){
            for(int i = 0 ; i < pTable.length ; i ++){
                pTable[i] = 0;
            }
            for(int i = 0 ; i < p.length() ; i ++){
                pTable[p.charAt(i) - 'a'] ++;
            }
        }
    }

[209.]: https://leetcode-cn.com/problems/minimum-size-subarray-sum/
[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[438.]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/