模板
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0;for (; right < nums.length; right++) {// 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)// 如果窗口达到固定长度，对于固定长的滑动窗口使用if来判断条件和改变窗口大小if(right - left + 1 == 窗口) { // 窗口和长度的比例需要根据题目判断// 更新 (部分或所有) 维护变量// 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变}// 使用while是对于不固定长的滑动窗口// 如果不符合条件，进行移动滑动窗口while (sum >= target) {// 更新 (部分或所有) 维护变量// 不断移动窗口左指针直到窗口再次合法}}return 结果;}}
适用题型
数组求字串，字符串的字串问题，在出现次数的提醒中，可能涉及到哈希表的使用。
固定的滑动窗口
209.长度最小的子数组
以经典题为例：(力扣链接🔗)
暴力解法:
使用两次for循环即可，然后不断的寻找符合条件的子序列，时间复杂度很明显是#card=math&code=O%28n%5E2%29&id=Lg2lP)。
class Solution {public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX; // 最终的结果int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为isum = 0;for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为jsum += nums[j];if (sum >= s) { // 一旦发现子序列和超过了s，更新resultsubLength = j - i + 1; // 取子序列的长度result = result < subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break}}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}};
滑动窗口法:
滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将#card=math&code=O%28n%5E2%29&id=dAC46)的暴力解法降为
#card=math&code=O%28n%29&id=bXs6s)。
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0, sum = 0, result = Integer.MAX_VALUE;for (; right < nums.length; right++) {sum += nums[right];// 如果大于则进行移动滑动窗口while (sum >= target) {// 取最小序列的长度result = Math.min(result, right - left + 1);// 移动滑动窗口sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}}
找到字符串中所有字母异位词
题目描述：
找到字符串中所有字母异位词（力扣链接🔗）
题目分析：
此题需要在p的固定长度下对s进行遍历判断，此时在遍历s进行范围判断，可以使用滑动窗口的方法，但此时滑动窗口的长度是固定的，在判断固定长度的字符串是否相等，可以映射在一个数组中判断即可（使用数组表示hashtable）。
代码：
/*** 使用固定的滑动窗口和hash表即可** @param s* @param p* @return*/public List<Integer> findAnagrams(String s, String p) {int[] record = new int[26]; // hash表记录重复的字符// 将p放入hash表中进行判断for (int i = 0; i < p.length(); i++) {record[p.charAt(i) - 'a']++;}int right = 0;int left = 0;List<Integer> list = new ArrayList<>();// 滑动窗口中的字符映射的数组int[] windows = new int[26];while (right < s.length()) {// 将字符放入数组windows[s.charAt(right) - 'a']++;// 在固定的滑动窗口进行判断if (right - left + 1 == p.length()) {// 如果窗口中的hash数组和p的hash数组相等，即将窗口左侧加入即可if (Arrays.equals(windows, record)) {list.add(left);}// 窗口不匹配时// 因为是固定长度，将left中的字符删除，将left向右移动即可windows[s.charAt(left) - 'a']--;left++;}right++;}return list;}}
643.子数组的最大平均数
class Solution {// 滑动窗口 子数组最大平均数 Ipublic double findMaxAverage(int[] nums, int k) {int sum = 0, left = 0, right = 0;double avg = Double.MIN_EXPONENT;for (; right < nums.length; right++) {sum += nums[right];if (right - left + 1 == k) {avg = Math.max(sum * 1.0 / k, avg);sum -= nums[left];left++;}}return avg;}}
438. 找到字符串中所有字母异位词
字符串适用哈希表时可以使用数组标识哈希表，需要整个进行判断的时候方便。
class Solution {/*** 失败（超时wuwu~~）想复杂了* @param s* @param p* @return*//*public List<Integer> findAnagrams(String s, String p) {HashMap<Object, Integer> map = new HashMap<>();List<Integer> list = new ArrayList<>();int left = 0, right = 0;map = toMap(p);while (left < s.length() && right < s.length()) {if (right - left < p.length()) {if (map.containsKey(s.charAt(right))) {map.put(s.charAt(right), map.getOrDefault(s.charAt(right), 0) - 1);// 等于0，直接清除if (map.get(s.charAt(right)) == 0) {map.remove(s.charAt(right));}}if (map.size() == 0) {list.add(left);left++;right = left;// 重新将p放入mapmap = toMap(p);}else {right++;}} else {left++;right = left;// 更新mapmap = toMap(p);}}return list;}public HashMap<Object, Integer> toMap(String str) {HashMap<Object, Integer> map = new HashMap<>();// 将p字符放入map中进行判断for (int i = 0; i < str.length(); i++) {map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);}return map;}*//*** 固定的滑动窗口** @param s* @param p* @return*//*public List<Integer> findAnagrams(String s, String p) {int[] record = new int[26]; // hash表记录重复的字符// 将p放入hash表中进行判断for (int i = 0; i < p.length(); i++) {record[p.charAt(i) - 'a']++;}int right = 0;int left = 0;List<Integer> list = new ArrayList<>();// 滑动窗口中的字符映射的数组int[] windows = new int[26];while (right < s.length()) {// 将字符放入数组windows[s.charAt(right) - 'a']++;// 在固定的滑动窗口进行判断if (right - left + 1 == p.length()) {// 如果窗口中的hash数组和p的hash数组相等，即将窗口左侧加入即可if (Arrays.equals(windows, record)) {list.add(left);}// 窗口不匹配时// 因为是固定长度，将left中的字符删除，将left向右移动即可windows[s.charAt(left) - 'a']--;left++;}right++;}return list;}*//*** TODO 使用固定的滑动窗口和hash表即可** @param s* @param p* @return*/public List<Integer> findAnagrams(String s, String p) {// p的hash表int[] record = new int[26];// 滑动窗口的哈希表int[] window = new int[26];List<Integer> indexList = new ArrayList<>();// 先将p放入哈希表for (int i = 0; i < p.length(); i++) {record[p.charAt(i) - 'a'] += 1;}// 左右窗口滑动int left = 0, right = 0;for (; right < s.length(); right++) {// 右界的字符加入哈希表window[s.charAt(right) - 'a'] += 1;// 固定的滑动窗口，不用whileif (right - left + 1 == p.length()) {// 两个哈希表相等，说明找到了，使用mao和set不是很容易判断if (Arrays.equals(window, record)) {// 此时记录最左边的索引indexList.add(left);}// 修改滑动窗口的哈希表window[s.charAt(left) - 'a'] -= 1;// 窗口向右移动，不满足同分异构也要移动窗口，保持固定的滑动窗口left++;// for循环就不用 right++ 了}}return indexList;}}
567. 字符串的排列
class Solution {/*** TODO 固定大小的滑动窗口** @param s1* @param s2* @return*/public boolean checkInclusion(String s1, String s2) {// s1的hash表int[] record = new int[26];// 滑动窗口的哈希表int[] window = new int[26];// 先将s1放入哈希表for (int i = 0; i < s1.length(); i++) {record[s1.charAt(i) - 'a'] += 1;}int left = 0, right = 0;for (; right < s2.length(); right++) {window[s2.charAt(right) - 'a'] += 1;// 固定大小的滑动窗口if (right - left + 1 == s1.length()) {if (Arrays.equals(window, record)) {// 返回true即可return true;}window[s2.charAt(left) - 'a'] -= 1;left++;}}return false;}}
487. 最大连续1的个数 II
class Solution {/*** 移动的滑动窗口** @param nums* @param k* @return*/public int longestOnes(int[] nums, int k) {// 最大长度int maxLength = 0;// 0的个数int count = 0;int left = 0, right = 0;for (; right < nums.length; right++) {// 0的个数加一if (nums[right] == 0) {count++;}// 如果大于可以填充的k，那么该移动窗口了，移动到k为0while (count > k) {if (nums[left] == 0) {// 0的个数减一count--;}// 移动窗口left++;}// 计算最大长度maxLength = Math.max(maxLength, right - left + 1);}return maxLength;}}
1052. 爱生气的书店老板
由于「技巧」只会将情绪将「生气」变为「不生气」，不生气仍然是不生气。
- 我们可以先将原本就满意的客户加入答案，同时将对应的 customers[i] 变为 0。
- 之后的问题转化为：在 customers中找到连续一段长度为 minutes 的子数组，使得其总和最大。这部分就是我们应用技巧所得到的客户。
class Solution {/*** 固定的滑动窗口** @param customers* @param grumpy* @param minutes* @return*/public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {// 先计算不生气就能让顾客满意数量int ans = 0; // 最大顾客for (int i = 0; i < customers.length; i++) {if (grumpy[i] == 0) {ans += customers[i];customers[i] = 0; // 并将满意顾客设为0}}int left = 0, right = 0;int cur = 0; // 当前满意度总数int max = 0; // 在生气的情况下，当前最大满意度// 此时在通过固定的滑动窗口来寻找生气最大的顾客满意数for (; right < customers.length; right++) {cur += customers[right];if (right - left == minutes) {cur -= customers[left];left++;}max = Math.max(max, cur);}return max + ans;}}
1423. 可获得的最大点数
这题相比前面的题目加了一丢丢小的变通: 题目要求首尾串最大点数，其实就是求非首尾串的连续序列的最小点数，转化过来就是求那几张牌之外作为的窗口，来查找最小的窗口，此时窗口是连起来的，反过来就可以从头尾找到最大的点数。
class Solution {/*** 固定的滑动窗口* 这题相比前面的题目加了一丢丢小的变通: 题目要求首尾串最大点数，其实就是求非首尾串的连续序列的最小点数** @param cardPoints* @param k* @return*/public int maxScore(int[] cardPoints, int k) {// 先计算出总和int sum = 0;for (int cardPoint : cardPoints) {sum += cardPoint;}// 特殊情况if (cardPoints.length == k) return sum;int minPoint = Integer.MAX_VALUE, curPoint = 0;int left = 0, right = 0; // 从第二个开始，去掉首尾,找中间的最大窗口for (; right < cardPoints.length; right++) {curPoint += cardPoints[right];// 移动窗口，找到窗口最小值if (right - left + 1 == (cardPoints.length - k)) {minPoint = Math.min(curPoint, minPoint);curPoint -= cardPoints[left];left++;}}return sum - minPoint;}}
变化的滑动窗口
水果成篮
题目描述（力扣链接）
解题方法
使用哈希表来判断是否重复，使用滑动窗口来更新范围。
class Solution {public int totalFruit(int[] fruits) {// 使用hashMap判断是否重复HashMap<Integer, Integer> map = new HashMap<>();int right = 0, left = 0, result = 0;for (; right < fruits.length; right++) {// 将遍历的元素放入map中map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);// 如果其中map的长度超过三，则滑动窗口while (map.size() > 2) {// 将left的取值减一map.put(fruits[left], map.get(fruits[left]) - 1);// 如果left的数量为0之后，则直接清除if (map.get(fruits[left]) == 0) map.remove(fruits[left]);left++;}// 获取其中取得最大的范围result = Math.max(result, right - left + 1);}return result;}}
最小覆盖子串
题目描述（力扣链接）
解题方法:
使用2个哈希表分别记录2个字符串中得词频情况进行判断，使用left和right两个指针在左闭右开的区间进行滑动，当包含t中所有的字符时停止滑动，进行判断，更新结果，再继续进行滑动。
class Solution {public String minWindow(String s, String t) {// 记录窗口中的词频数量HashMap<Character, Integer> window = new HashMap<>();// 记录t中的所有字符，用来查询是否存在HashMap<Character, Integer> map = new HashMap<>();// count为s中包含t字符的个数，result为最小字符串的大小, start记录最小字符串开始的位置int left = 0, right = 0, count = 0, result = Integer.MAX_VALUE, start = 0;// 将t中的字符串全部放入map中for (int i = 0; i < t.length(); i++) {map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);}// 循环进行判断while (right < s.length()) {// 如果map中含有该字符，将字符的value值加一，并且将count加一if (map.containsKey(s.charAt(right))) {window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);if (map.get(s.charAt(right)).equals(window.get(s.charAt(right)))) {count++;}}// 移动窗口右侧进行遍历right++;// 当计数器等于t的大小时，此时窗口需要移动while (count == map.size()) {// 如果窗口大小小于上一个窗口的大小，进行赋值if (right - left < result) {result = right - left;start = left;}// 移动窗口if (map.containsKey(s.charAt(left))) {// 如果window中的值和map中的值数量相等才是包含t的字串if (window.get(s.charAt(left)).equals(map.get(s.charAt(left)))) {count--;}// 将窗口中保存值的数量减一window.put(s.charAt(left), window.getOrDefault(s.charAt(left), 0) - 1);}left++;}}return result == Integer.MAX_VALUE ? "" : s.substring(start, start + result);}}
3.无重复字符的最长子串
class Solution {// 固定滑动窗口public int lengthOfLongestSubstring(String s) {// 定义需要维护的变量，本题要求是最大长度，所以需要定义maxLength，该题又涉及去重，因此还需要一个哈希表Set<Character> set = new HashSet<>();int left = 0, right = 0, maxLength = 0;for (; right < s.length(); right++) {// 更新需要维护的变量（max_len和HashSet）while (set.contains(s.charAt(right))) {set.remove(s.charAt(left));left++;}maxLength = Math.max(right - left + 1, maxLength);set.add(s.charAt(right));}return maxLength;}}
159. 至多包含两个不同字符的最长子串
class Solution {/*public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0, sum = 0, result = Integer.MAX_VALUE;for (; right < nums.length; right++) {sum += nums[right];// 如果大于则进行移动滑动窗口while (sum >= target) {// 取最小序列的长度result = Math.min(result, right - left + 1);// 移动滑动窗口sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}*//*** 滑动窗口* 时间复杂度O(n)** @param target* @param nums* @return*/public int minSubArrayLen(int target, int[] nums) {int result = Integer.MAX_VALUE;int sum = 0; // 表示总和int left = 0; // 左边窗口边界for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= target) {sum -= nums[left];result = Math.min(result, right - left + 1);left++;}}return result == Integer.MAX_VALUE ? 0 : result;}}
1695. 删除子数组的最大得分
class Solution {/*** 滑动窗口** @param nums* @return*/public int maximumUniqueSubarray(int[] nums) {// 定义需要维护的变量Set<Integer> set = new HashSet<>();int total = 0, max_total = 0;// 定义窗口的首尾端（start，end），然后滑动窗口int left = 0, right = 0;for (; right < nums.length; right++) {// 更新需要维护的变量while (set.contains(nums[right])) {set.remove(nums[left]);total -= nums[left];left++;}total += nums[right];max_total = Math.max(total, max_total);set.add(nums[right]);}return max_total;}}
1208. 尽可能使字符串相等
class Solution {/*** TODO 移动的滑动窗口** @param s* @param t* @param maxCost* @return*/public int equalSubstring(String s, String t, int maxCost) {// 差值总和int difference = 0;// 最大长度的int maxLength = 0;int left = 0, right = 0;for (; right < s.length(); right++) {difference += Math.abs(s.charAt(right) - t.charAt(right));// 大于转换量，此时就需要移动窗口while (difference > maxCost) {difference -= Math.abs(s.charAt(left) - t.charAt(left));left++;}maxLength = Math.max(maxLength, right - left + 1);}return maxLength;}}
剑指 Offer 57 - II. 和为 s 的连续正数序列
https://leetcode.cn/leetbook/read/illustration-of-algorithm/eufzm7/
设连续正整数序列的左边界 i 和右边界 j ，则可构建滑动窗口从左向右滑动。循环中，每轮判断滑动窗口内元素和与目标值 target 的大小关系，若相等则记录结果，若大于 target 则移动左边界 i （以减小窗口内的元素和），若小于 target 则移动右边界 j（以增大窗口内的元素和）。
注意返回的是 int [][] 数组，那么此时可以申请为List
class Solution {public int[][] findContinuousSequence(int target) {int left = 1, right = 1;List<int[]> res = new ArrayList<>();for (; left < target; left++) {// 初始化总和int sum = left;for (right = left + 1; right < target; right++) {sum += right;if (sum < target) {// for已经加了} else if (sum == target){// 窗口满足// 此时相加大于了target，保存连续序列int count = 0;int[] array = new int[right - left + 1];for (int i = left; i <= right; i++, count++) {array[count] = i;}res.add(array);}else if (sum > target) {// 窗口不满足移动左边窗口break;}}}return res.toArray(new int[0][]);}}
若有收获，就点个赞吧
0 人点赞
