数据结构与算法：滑动窗口类题目总结

滑动窗口类型题目解题框架总结：

class Solution:
    def problemName(self, s: str) -> int:
        # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
        x, y = ..., ...


        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(s)):
            # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
            x = new_x
            if condition:
                y = new_y


            '''
            ------------- 下面是两种情况，读者请根据题意二选1 -------------
            '''
            # Step 4 - 情况1
            # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 
            # 如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, 
            # 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 
            if 窗口长度达到了限定长度:
                # 更新 (部分或所有) 维护变量 
                # 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变


            # Step 4 - 情况2
            # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while 不合法:
                # 更新 (部分或所有) 维护变量 
                # 不断移动窗口左指针直到窗口再次合法


        # Step 5: 返回答案
        return ...

1、无重复字符的最长子串（leetcode-003）

给定一个字符串 ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 :
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

    // 双指针，滑动窗口(时间复杂度n)
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLongestSubstring(String s) {

            //判断处理空字符
            if (s==null || s.length() == 0){
                return 0;
            }
            // step1:定义需要维护的变量，最小子串数量，哈希表存储字符与字符位置
            int ans = 0;
            Map<Character, Integer> map = new HashMap<>();
            // step2:定义左右两个指针，滑动右指针
            for (int start = 0,end = 0;end<s.length();end++){
                char element = s.charAt(end);
                // step3:如果出现重复字符，则移动左指针，确保左指针必须右移，需要max筛选防止左移
                if (map.containsKey(element)){
                    start = Math.max(start,map.get(element)+1);
                }
                // step4:更新维护变量
                ans = Math.max(ans,end-start+1);
                map.put(element,end);
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

2.子数组最大平均数 I（leetcode-643）

给你一个由n个元素组成的整数数组nums和一个整数k 。
请你找出平均数最大且 长度为k的连续子数组，并输出该最大平均数。
示例:
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

    /**
     * 滑动窗口套路题
     */
    class Solution {
        public double findMaxAverage(int[] nums, int k) {
            //定义需要维护的变量，求和与平均值
            double sum = 0;
            double max_avg = -999999;
            // 定义窗口首末端，并且滑动末端窗口
            for (int start=0,end=0;end<nums.length;end++){
                sum+=nums[end];
                //更新需要维护的变量
                if (end-start+1==k){
                    max_avg = Math.max(max_avg,sum / k);
                }
                // 窗口长度固定，则首指针前移，同时维护变量
                if (end>=k-1){
                    sum-=nums[start];
                    start+=1;
                }
            }
            //返回结果
            return max_avg;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

3.至多包含两个不同字符的最长子串(leetcode-159)

在这里插入图片描述

public static int lengthOfLongestSubstringTwoDistinct(String s) {
  //定义需要维护的变量，最长字串长度，map存储字符和位置
  int ans = 0;
  Map<Character,Integer> map = new HashMap<>();


  // 定义两个窗口两个指针，滑动末端指针
  for (int start=0,end=0;end<s.length();end++){
    //step3:更新维护变量，map存储字符与位置
    char element = s.charAt(end);
    map.put(element,end);
    if (map.size()<=2) {
      ans = Math.max(ans,end-start+1);
    }
    // step4：如果哈希表长度等于 说明出现三个重复字符，则获取最左字符位置+1作为左指针
    if (map.size() == 3){
      int delId = Collections.min(map.values());
      map.remove(s.charAt(delId));
      start = delId+1;
    }
    ans = Math.max(ans,end-start+1);
  }
  return ans;
}
public static void main(String args[]){

  String s = "ccaabbb";
  int data = new LengthOfLongestSubstringTwoDistinct().lengthOfLongestSubstringTwoDistinct(s);
  System.out.println(data);

}

4.长度最小的子数组(leetcode-209)

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长
度。如果不存在符合条件的子数组，返回 0 。

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

//输入：target = 11, nums = [1,1,1,1,1,1,1,1]
//输出：0

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minSubArrayLen(int target, int[] nums) {

        // 定义需要维护的变量，包括最小长度和数组求和
        int ans = 999999,sum=0;
        // 定义数组首尾指针，并且滑动窗口(end指针移动)
        for (int start =0,end=0;end<nums.length;end++){
            // 更新需要维护的变量
            sum += nums[end];
            // 如果求和大于等于目标值则需要移动左指针,同时更新维护变量
            while(sum>=target){
                ans = Math.min(ans,end-start+1);
                sum -= nums[start];
                start+=1;
            }
        }
        if(ans==999999){
            return 0;
        }
        return ans;
    }
}

5.删除子数组的最大得分（leetcode-1659）

//给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。返回 只删除一个 子数组可获得的 最大得分 。 如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例:
//输入：nums = [4,2,4,5,6]
//输出：17
//解释：最优子数组是 [2,4,5,6]
// 
//输入：nums = [5,2,1,2,5,2,1,2,5]
//输出：8
//解释：最优子数组是 [5,2,1] 或 [1,2,5]

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maximumUniqueSubarray(int[] nums) {

        // step1:定义维护变量当前得分和最大得分
        int sum =0,sum_max = 0;
        Map<Integer,Integer> map = new HashMap<>();


        //step2:定义左右指针，并且移动右指针
        for (int start = 0,end =0;end<nums.length;end++){
            //step3:更新维护变量,哈希表验证是否存在重复值
            sum +=nums[end];
            map.put(nums[end],map.getOrDefault(nums[end],0)+1);
            // 判断不存在重复值,
            if (end-start+1 == map.size()){
                sum_max = Math.max(sum,sum_max);
            }
            //step4:如果子数组存在重复值，需要左侧收缩，直到窗口合法(确保窗口合法)
            while(end-start+1 > map.size()){
                int head = nums[start];
                map.put(head,map.get(head)-1);
                if (map.get(head)==0){
                    map.remove(head);
                }
                sum -= nums[start++];
            }
        }
        return  sum_max;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

6.找到字符串中所有字母异位词（leetcode-438）

//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 
// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

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

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> findAnagrams(String s, String p) {


        //step1:定义维护变量，存储结果数组以及哈希表对比字符串是否为异位词
        List<Integer> ans = new ArrayList();
        Map<Character,Integer> map = new HashMap<>();
        Map<Character,Integer> mapp = new HashMap<>();


        //step1.1:构建字符串p的哈希表
        for (int i=0;i<p.length();i++){
            mapp.put(p.charAt(i),mapp.getOrDefault(p.charAt(i),0)+1);
        }
        //step2:定义左右窗口指针，滑动右指针
        for (int start=0,end=0;end<s.length();end++){
            // step3:更新需要维护的变量,如果两个哈希表相等，则保存一个解
            map.put(s.charAt(end),map.getOrDefault(s.charAt(end),0)+1);
            if (map.equals(mapp)){
                ans.add(start);
            }


            //step4：由于窗口长度固定，if判断来维护固定长度窗口，并且左指针右移
            if (end-start+1>=p.length()){
                map.put(s.charAt(start),map.get(s.charAt(start))-1);
                if (map.get(s.charAt(start))==0){
                    map.remove(s.charAt(start));
                }
                start++;
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

7. 字符串的排列（leetcode-567）


//给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。 
// 换句话说，s1 的排列之一是 s2 的 子串 。 

// 示例 1：
//输入：s1 = "ab" s2 = "eidbaooo"
//输出：true
//解释：s2 包含 s1 的排列之一 ("ba").


    /**
     * 思路：使用滑动窗口从s2中找到字符串s1的任意排列
     */


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean checkInclusion(String s1, String s2) {


            // step1：定义维护变量，哈希表存储字符串
            Map<Character,Integer> map = new HashMap<>();


            //step1.1:同时尽力字符串s1的哈希表
            Map<Character,Integer> maps1 = new HashMap<>();


            for (int i=0;i<s1.length();i++){
                maps1.put(s1.charAt(i),maps1.getOrDefault(s1.charAt(i),0)+1);
            }


            // step2:定义窗口左右指针，并且移动右指针
            for (int start=0,end=0;end<s2.length();end++){
                //step3:更新维护变量,判断两个map知否相等决定是否包含
                map.put(s2.charAt(end),map.getOrDefault(s2.charAt(end),0)+1);
                if (map.equals(maps1)){
                    return true;
                }
                //step4:由于窗口长度固定，因此用if判断维护固定窗口，同时左指针右移动
                if (end-start+1>=s1.length()){
                    //左指针移动，移动之前要更新维护变量
                    map.put(s2.charAt(start),map.get(s2.charAt(start))-1);
                    if (map.get(s2.charAt(start))==0){
                        map.remove(s2.charAt(start));
                    }
                    start++;
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

8. 最大连续1的个数（leetcode-487,1004）


给定一个二进制数组，你可以最多将 1，k个 0 翻转为 1，找出其中最大连续 1 的个数。
示例 1：
输入：[1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
     当翻转以后，最大连续 1 的个数为 4。
 

注：
输入数组只包含 0 和 1.
输入数组的长度为正整数，且不超过 10,000

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestOnes(int[] nums, int k) {
            //step1:定义维护变量，最大1个数以及哈希表统计0，1个数
            int max = 0;
            Map<Integer,Integer> map = new HashMap<>();
    
            // step2:定义左右指针，滑动右指针
            for (int start=0,end=0;end<nums.length;end++){
    
                //step3:更新维护变量,如果0的个数小于等于k则更新max
                map.put(nums[end],map.getOrDefault(nums[end],0)+1);
                if (map.getOrDefault(0,0)<=k){
                    max = Math.max(max,end-start+1);
                }
                //step4:窗口不固定，需要移动左指针确保窗口合法
                while(map.getOrDefault(0,0)>k){
                    map.put(nums[start],map.get(nums[start])-1);
                    start++;
                }
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

9. 爱生气的老板（leetcode-1052）

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客的编号，所有这些顾客在第 i 分钟结束后离开。
在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。请你返回这一天营业下来，最多有多少客户能够感到满意。

// 示例 1：

//输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
//输出：16
//解释：书店老板在最后 3 分钟保持冷静。
//感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {

            //step1:定义需要维护的变量
            int sum = 0,maxsum = 0,startmax=0;
            //step2:定义窗口左右指针，滑动窗口移动右指针
            for (int start=0,end=0;end< customers.length;end++){
                //step3:更新需要维护的变量,确保minutes内让更多人满意
                if (grumpy[end]==1){
                    sum += customers[end];
                }
                if (maxsum<sum){
                    maxsum = sum;
                    startmax = start;
                }
                //step4:窗口长度，也就是在minutes分钟，窗口长度为minutes，用if确保窗口长度
                if (end-start+1 >= minutes){
                    if (grumpy[start] == 1){
                        sum -= customers[start];
                    }
                    start++;
                }
            }
            //step5:上述滑动窗口找到了老板开始生气的节点startmax；计算结果
            for (int i = startmax;i<startmax+minutes;i++){
                grumpy[i]=0;
            }
            int res = 0;
            for (int j = 0;j< customers.length;j++){
                if (grumpy[j]==0){
                    res+=customers[j];
                }
            }
            return res;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)

10.可获得的最大点数（leetcode-1423）

//几张卡牌排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
// 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
// 你的点数就是你拿到手中的所有卡牌的点数之和。
// 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

// 示例 1：
// 输入：cardPoints = [1,2,3,4,5,6,1], k = 3
//输出：12
//解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

/**
 * 本提要求首尾串的最大点数，也就是非首尾串的连续序列字串的最小和
 */
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxScore(int[] cardPoints, int k) {


        //step0:特解
        if (k==cardPoints.length){
            return Arrays.stream(cardPoints).sum();
        }
        //step1:定义需要维护的变量,m表示连续字串的窗口大小
        int m = cardPoints.length-k;
        int min_sum = Integer.MAX_VALUE,sum=0;


        // step3:定义左右指针，移动窗口
        for (int start=0,end=0;end<cardPoints.length;end++){


            // step4:更新维护变量
            sum += cardPoints[end];
            //step5:窗口长度固定，用if判断维护窗口合法，并且移动左指针
            if (end-start+1>=m){
                min_sum = Math.min(min_sum,sum);
                sum -= cardPoints[start];
                start++;
            }
        }
        int sumlist = 0;
        for (int j= 0;j<cardPoints.length;j++){
            sumlist+=cardPoints[j];
        }


        return sumlist-min_sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)