滑动窗口算法 总结（附经典题目）

6.滑动窗口

求满足一定条件的 连续子区间，子串一般用滑动窗口

模板

public slidingWindow(String s, String t){
    HashMap<Character,Integer> need,window;
    for(char c: t.toCharArray()){
        need.put(c,need.getOrDefault(c,0)+1);
    }
    int left right valid=0;
    while(right<s.length()){
        //当前字符
        char c=s.getCharAt(right);
        //增大右窗口
        right++;
        
        //进行窗口内数据的更新
        ...
       //判断左窗口是够需要收缩
        while(window needs shrink){
            char d=t.charAt(left);
            left++;
            //进行窗口数据的更新
            ...
        }
        
    }
}

最后返回原字符串的[left,right)

题目：长度最小的子数组

解法：

我们以该题为例

我们依次增大右边界，直到满足条件后，增大左边界缩小区间，直到不满足条件后再次增大右边界......

时间复杂度O（N）

 public int minSubArrayLen(int target, int[] nums) {
      if(nums.length==0){
          return 0;
      }
      int left=0;
      int right=0;
      int sum=0;
      int result=Integer.MAX_VALUE;
      //通常主循环是以右边界为判断条件
      while(right<nums.length){
          sum=sum+nums[right];
          //满足条件后开始增大左边界
          while(sum>=target){
              result=Math.min(result,right-left+1);
              sum=sum-nums[left];
              left++;
          }
          right++;
      }
     // 如果没有满足条件的区间，返回0
      return result==Integer.MAX_VALUE? 0:result;

    }

题目：无重复字符最长子串

解法：

 public int lengthOfLongestSubstring(String s) { 
        if(s.length()==0){
            return 0;
        }
        //存储已经访问过的字符
        HashMap<Character,Integer> hashMap=new HashMap<>();
        int right=0;
        int left=0;
        int result=Integer.MIN_VALUE;

        while (right < s.length()) {
            char c=s.charAt(right);
           
            right++;
            hashMap.put(c,hashMap.getOrDefault(c,0)+1);

            //左边界更新
            //这里要用equals,因为Integer类型比较的是地址（如果是[-127，128]内的数字，由于缓存存在，地址相同，此时equals和==无区别，但超过这个范围地址就不同了）
            while(hashMap.get(c).equals(2)){
                
                char b=s.charAt(left);
                left++;
                hashMap.put(b,hashMap.get(b)-1);
            }
           result=Math.max(right-left,result);
        }
        
        return result;
    }

题目：字符串排列

解法

public boolean checkInclusion(String s1, String s2) {
        HashMap<Character,Integer> need=new HashMap<>();
        HashMap<Character,Integer> window=new HashMap<>();
        int right=0;
        int left=0;
        int valid=0;
        for(char c: s1.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        while(right<s2.length()){
            char c=s2.charAt(right);
            right++;
            
            if(need.containsKey(c)){
               window.put(c,window.getOrDefault(c,0)+1);
               
               if(window.get(c).equals(need.get(c))){
                   valid++;
               }
            }
            while(valid==need.size()){
                if(right-left==s1.length()){
                    return true;
                }
                char b=s2.charAt(left);
                left++;
                if (need.containsKey(b)) {
                if(window.get(b).equals(need.get(b))){
                    valid--;
                }
                window.put(b,window.getOrDefault(b,0)-1);
            }
            }
        }
        return false;
    }

题目：找到字符串中所有字母异位词

解法：

public List<Integer> findAnagrams(String s, String p) {
          List<Integer> result=new ArrayList<>();
          HashMap<Character,Integer> need=new HashMap<>();
          HashMap<Character,Integer> window=new HashMap<>();
          for(char c:p.toCharArray()){
              need.put(c,need.getOrDefault(c,0)+1);
          }
          int right=0;
          int left=0;
          int valid=0;
          while(right<s.length()){
              char c=s.charAt(right);
              right++;
              if(need.containsKey(c)){
                  window.put(c,window.getOrDefault(c,0)+1);
                  if(window.get(c).equals(need.get(c))){
                      valid++;
                  }
              }
              //开始收缩左边界
              while(valid==need.size()){
                  if(right-left==p.length()){
                      result.add(left);
                  }
                  char b=s.charAt(left);
                  left++;
       
                  if(need.containsKey(b)){
                    //如果当前数目刚好够，减一次就不够了
                     if(window.get(b).equals(need.get(b))){
                          valid--;
                      }
                      window.put(b,window.getOrDefault(b,0)-1);
                     
                  }
              }            
          }
          return result;
    }

题目：最小覆盖子串

解法：

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<Character, Integer>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (char c :  t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);

        int left = 0, right = 0;
        int valid = 0;
        // 记录最小覆盖字串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 判断取出的字符是否在字串中
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c,0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 判断是否需要收缩（已经找到合适的覆盖串）
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char c1 = s.charAt(left);
                left++;
                if (need.containsKey(c1)) {
                    if (window.get(c1).equals(need.get(c1))) {
                        valid--;
                    }
                     window.put(c1, window.getOrDefault(c1, 0) - 1);
                }

            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

}

滑动窗口算法 总结（附经典题目）

原文：https://www.cnblogs.com/wangstudyblog/p/14690633.html