算法问题——滑动窗口问题集合

大佬的博客：https://blog.csdn.net/qq_43152052/article/details/102840715 我这里做一个笔记和整理

滑动窗口思想： ①）窗口由两个指针构成，一个左指针left，一个右指针right，然后[left,right]表示的索引范围是一个窗口了。

②）右指针right的功能是用来扩展窗口：当窗口内的条件没有达到题目要求时，我们需要不断移动右指针right直到窗口内的条件第一次满足题目要求为止。

③）左指针left的功能是用来缩小窗口的：当窗口内的条件已满足题目条件或多于题目条件时（窗口溢出），我们缩小窗口，也就是左指针left需要右移直到窗口条件不满足为止。这时，我们需要记录当前窗口的大小，并更新目前为止满足条件的最小窗口记录。之后，再次扩展右指针right，使得窗口满足题目的条件。

注：滑动窗口用来处理连续满足一定条件的连续区间的性质（长度等）问题的，两个指针都起始于原点，并一前一后向终点前进。

滑动窗口的解题思路 ：

1左右都是从开始的时候设置为0的时候开始

2开始右指针移动，并且找在窗口中找到服务的

3这个时候右边指针停止 左边指针开始移动。如果窗口不满足要求的话，那就是左指针他停止，右指针开始移动。

4 一直到右边指针遍历到最后的位置借宿整个循环 并判断是是否需要求解的条件。

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

思路是:暴力就是直接采用的多次遍历就可以实欢动窗口的最大或者是最小的数据。

方法一： 重头开始遍历两次 利用的set 来保存当前的不重复的元素的，并且每一次都去比较最大的set的最大的值并返回。

二：利用双指针的思想来开始遍历，开始是右边的走，一直到看到遇见相同的时候 这个时候开始左边的指针开始走。当左边的和右边的时候相同的时候右边 的有开始走，当右边的走到结束了这表示的遍历结束了。

/**
 * Copyright (C), 2018-2020
 * FileName: 无重复的字符的最长字串
 * Author:   xjl
 * Date:     2020/9/2 22:19
 * Description:
 */
package 滑动窗口问题集合;

import java.util.HashSet;
import java.util.Set;

public class 无重复的字符的最长字串 {
    /**
     * 相当于是的暴力的求解相关方法
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        //用来记录的这个不重复的字符
        for (int i = 0; i < s.length(); i++) {
            Set set = new HashSet();
            //这还是采用的遍历的全部的数据的方式
            for (int j = i; j < s.length(); j++) {
                if (!set.contains(s.charAt(j))) {
                    res = Math.max(res, j - i + 1);
                    set.add(s.charAt(j));
                } else {
                    break;
                }
            }
        }
        return res;
    }

    /**
     * 采用的是双指针的一种方式来实现的窗口的不重复性的元素  利用的set 维护了一个窗口
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {
        int res = 0;
        int l = 0;
        int r = 0;
        Set set = new HashSet();
        //开始有指针开始移动
        while (r < s.length()) {
            //如果右一直走 一直到遇见重复的元素
            while (r < s.length() && !set.contains(s.charAt(r))) {
                set.add(s.charAt(r));
                r++;
            }
            //比较当前的res 和 r-l的就是滑动窗口的大小
            res = Math.max(res, set.size());
            //如果右边走到最后了 整个就结束
            if (r == s.length()) {
                break;
            }
            //当l= k - 1) {
                result.add(nums[deque.getFirst()]);
            }
        }
        int[] ans = new int[result.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = result.get(i);
        }
        return ans;
    }
}

76. 最小覆盖子串

424. 替换后的最长重复字符

package 滑动窗口问题集合;

public class 替换后的最长重复字符424 {
    public int test(String s, int k) {
        //设置窗口的左右
        int left = 0;
        int right = 0;

        int result = 0;
        //最多的重复字母的个数
        int maxlen = -1;
        //设置元素的个数
        char[] chars = new char[256];
        //当有边界小于的最后的时候结束循环
        while (right < s.length()) {
            //获取当前元素
            char cur = s.charAt(right);
            //表示的是的A的元素的个数+1
            chars[cur]++;
            //获取最多元素的个数和
            maxlen = Math.max(maxlen, chars[cur]);
            //如果是超过的k个数的不同
            while ((right - left + 1 - maxlen) > k) {
                //左边开始++ 并将元素个数减1
                chars[s.charAt(left++)]--;
            }
            //表示替换后的数组可以实现的一种最多
            result = Math.max(result, right - left + 1);
            right++;
        }
        return result;
    }
}

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

package 滑动窗口问题集合;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class 找到字符串中所有字母异位词438 {

    public List findAnagrams(String s, String p) {
        int start = 0, left = 0, right = 0;
        int macth = 0;
        List res = new ArrayList();
        //表示窗口和当前的须的条件
        HashMap window = new HashMap();
        HashMap needs = new HashMap();

        for (char c : p.toCharArray()) {
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }
        //右指针移动
        while (right < s.length()) {
            char c1 = s.charAt(right);
            if (needs.containsKey(c1)) {
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1).equals(needs.get(c1)))
                    macth++;
            } else {
                //如果是不在里面将左指针跳到右指重新开始的窗口 并计数为0
                left = right + 1;
                window = new HashMap();
                macth = 0;
            }
            right++;
            //左指针开始移动
            while (macth == needs.size()) {
                start = left;
                if (window.equals(needs))
                    res.add(start);
                char c2 = s.charAt(left);
                if (window.containsKey(c2)) {
                    window.put(c2, window.get(c2) - 1);
                    if (window.get(c2) < (needs.get(c2)))
                        macth--;
                }
                left++;
            }
        }
        return res;
    }
}

480. 滑动窗口中位数

/**
 * Copyright (C), 2018-2020
 * FileName: 滑动窗口中位数480
 * Author:   xjl
 * Date:     2020/9/4 21:21
 * Description:
 */
package 滑动窗口问题集合;

import java.util.Collections;
import java.util.PriorityQueue;

public class 滑动窗口中位数480 {
    //使用了优先队列这样一个工具
    PriorityQueue maxHeap = new PriorityQueue((Collections.reverseOrder()));
    PriorityQueue minHeap = new PriorityQueue();

    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] result = new double[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if (maxHeap.size() == 0 || maxHeap.peek() >= nums[i]) {
                maxHeap.add(nums[i]);
            } else {
                minHeap.add(nums[i]);
            }
            balanceHeaps();
            if (i - k + 1 >= 0) {
                if (maxHeap.size() == minHeap.size()) {
                    result[i - k + 1] = maxHeap.peek() / 2.0 + minHeap.peek() / 2.0;
                } else {
                    result[i - k + 1] = maxHeap.peek();
                }

                int elementToBeRemoved = nums[i - k + 1];
                if (elementToBeRemoved  minHeap.size() + 1)
            minHeap.add(maxHeap.poll());
        else if (maxHeap.size() < minHeap.size())
            maxHeap.add(minHeap.poll());
    }
}

567. 字符串的排列

/**
 * Copyright (C), 2018-2020
 * FileName: 字符串的排列567
 * Author:   xjl
 * Date:     2020/9/5 16:20
 * Description:
 */
package 滑动窗口问题集合;

import java.util.Arrays;

public class 字符串的排列567 {

    public boolean checkInclusion(String s1, String s2) {
        //记录好两个长度
        int l1 = s1.length();
        int l2 = s2.length();
        //定义好这个数组的表示的a-z的个数
        int[] c1 = new int[26];
        int[] c2 = new int[26];
        //记录好s1的每一个字母的个数
        for (char c : s1.toCharArray()) {
            c1[c - 'a']++;
        }
        //开始遍历新的l2的长度 这时候开始右至指针
        for (int i = 0; i < l2; i++) {
            if (i >= l1) {
                --(c2[s2.charAt(i - l1) - 'a']);
            }
            c2[s2.charAt(i) - 'a']++;
            //判断两个数组时候相同 知识统计个数而不是统计顺序的什么的 应为是子序列
            if (Arrays.equals(c1, c2)) {
                return true;
            }
        }
        return false;
    }
}

992. K 个不同整数的子数组

 

995. K 连续位的最小翻转次数

 

978. 最长湍流子数组

 

1052. 爱生气的书店老板

 

1074. 元素和为目标值的子矩阵数量

 

1208. 尽可能使字符串相等