之前对于滑动窗口一直不太理解,感觉复杂,今天连续写了好几个滑动窗口的题目,还是感觉总结出了点规律,在这里分享给大家

int left = 0,right = 0;
while(right < n){
  // 扩大窗口,右指针往右移动
  window.put(s[right]);
  right++;
  // 缩小窗口,左指针往右移动
  while(满足条件){
    window.remove(s[left]);
    left++;
  }
}

下面分享几道练习题给大家,大家也可以参考我的代码。

904. 水果成篮

class Solution {
    public int totalFruit(int[] fruits) {
        if(fruits == null || fruits.length == 0) return 0;
        int i = 0,ans = 0,n = fruits.length;
        Map<Integer, Integer> map = new HashMap<>();

        for(int j = 0;j < n;j++){
            // 第一次就设置设为1，之后就++
            map.put(fruits[j],map.getOrDefault(fruits[j],0) + 1);
            // 滑动窗口内有两种以上的水果
            while(map.size() > 2){
                // 左边边界收缩
                map.put(fruits[i],map.get(fruits[i]) - 1);
                if(map.get(fruits[i]) == 0) map.remove(fruits[i]);
                i++;
            }
            ans = Math.max(ans,j-i+1);
        }
        return ans;
    }
}

class Solution {
    public int totalFruit(int[] fruits) {
        int ans = 0,left = 0,right = 0,n = fruits.length;
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        // 水果的种类
        int count = 0;
        while(right < n){
            int i1 = fruits[right];
            right++;
            hashMap.put(i1,hashMap.getOrDefault(i1,0)+1);
            // 仅当为1的时候才count++，是因为为1才表示，有新的类别的水果进框
            if(hashMap.get(i1) == 1) count++;
            while(count == 3){
                int i2 = fruits[left];
                left++;
                if(hashMap.get(i2) == 1) count--;
                hashMap.put(i2,hashMap.get(i2)-1);
            }
            ans = Math.max(right-left,ans);
        }
        return ans;
    }
}

76. 最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(),m = t.length(),minLen = Integer.MAX_VALUE;
        int left = 0,right = 0;
        int begin = 0,end = 0;
        Map<Character,Integer> needs = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
      // needs里面存的是字串应该有的所有字符
        for(int i = 0;i < m;i++) needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0)+1);
        int match = 0;
        // 滑动窗口扩张
        while(right < n){
            char ch1 = s.charAt(right);
            right++;
            // 字串中的字符
            if(needs.containsKey(ch1)){
                window.put(ch1,window.getOrDefault(ch1,0)+1);
                if(window.get(ch1).equals(needs.get(ch1))) match++;
            }
            // 涵盖了t中所有的字符
            while(match == needs.size()){
            // 更新
                if(minLen > right - left){
                    minLen = right - left;
                    begin = left;
                    end = right;
                }
                char ch2 = s.charAt(left);
                left++;
                if(needs.containsKey(ch2)){
                    window.put(ch2,window.getOrDefault(ch2,0)-1);
                    if(window.get(ch2) < needs.get(ch2)) match--;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(begin,end);
    }
}

567. 字符串的排列

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(),m = s2.length();
        int left = 0,right = 0;
        Map<Character,Integer> needs = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for(int i = 0;i < n;i++) needs.put(s1.charAt(i),needs.getOrDefault(s1.charAt(i),0)+1);
        int match = 0;
        while(right < m){
            char ch1 = s2.charAt(right);
            right++;
            if(needs.containsKey(ch1)){
                window.put(ch1,window.getOrDefault(ch1,0)+1);
                if(window.get(ch1).equals(needs.get(ch1))) match++;
            }
            while(right - left >= n){
                if(match == needs.size()) return true;
                char ch2 = s2.charAt(left);
                left++;
                if(needs.containsKey(ch2)){
                    if(window.get(ch2).equals(needs.get(ch2))) match--;
                    window.put(ch2,window.get(ch2)-1);
                }
            }
            
        }
        return false;
    }
}

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

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length(),m = p.length();
        int left = 0,right = 0,match = 0;
        Map<Character,Integer> needs = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for(int i = 0;i < m;i++) needs.put(p.charAt(i),needs.getOrDefault(p.charAt(i),0)+1);
        while(right < n){
            char ch1 = s.charAt(right);
            right++;
            if(needs.containsKey(ch1)){
                window.put(ch1,window.getOrDefault(ch1,0)+1);
                if(needs.get(ch1).equals(window.get(ch1))) match++;
            }
            if(right - left >= m){
                if(match == needs.size()) ans.add(left);
                char ch2 = s.charAt(left);
                left++;
                if(needs.containsKey(ch2)){
                    if(needs.get(ch2).equals(window.get(ch2))) match--;
                    window.put(ch2,window.getOrDefault(ch2,0)-1);
                }   
            }
        }
        return ans;
    }
}

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(),left = 0,right = 0,ans = 0;
        Map<Character,Integer> window = new HashMap<>();
        while(right < n){
            char ch1 = s.charAt(right);
            right++;

            window.put(ch1,window.getOrDefault(ch1,0)+1);

            while(window.get(ch1) > 1){
                char ch2 =s.charAt(left);
                window.put(ch2,window.get(ch2)-1);
                left++;
            }
            ans = Math.max(ans,right-left);
        }
        return ans;
    }
}