本文主要是介绍Sliding Windows，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
209，3，904，76，438，560，239
套路：
初始化左指针，初始化右指针，初始化窗口，初始化结果
右指针循环遍历扩大窗口
进行窗口判断
左指循环针遍历缩小窗口
最大值在扩窗时收集结果，最小值在缩窗时收集结果
template
import java.util.HashMap;public class SlidingWindow {public void slidingWindow(String s, String t) {HashMap<Character, Integer> need = new HashMap<>();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;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新// 例如：更新窗口内字符的计数window.put(c, window.getOrDefault(c, 0) + 1);// 当窗口内满足某些条件时进行调试输出System.out.println("window: [" + left + ", " + right + ")");// 判断左侧窗口是否要收缩while (window needs shrink) { // 这里的条件需要根据具体问题来定义// d 是将移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新// 例如：减少窗口内字符的计数window.put(d, window.getOrDefault(d, 1) - 1);}}}public static void main(String[] args) {SlidingWindow sw = new SlidingWindow();sw.slidingWindow("your_string_s", "your_string_t");}
}
209. 长度最小的子数组
中等
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。7
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
class Solution {// 方法：求最短的子数组，其和至少为 targetpublic int minSubArrayLen(int target, int[] nums) {int left = 0; // 左指针，用于标记子数组的开始位置int sum = 0; // 用于记录当前子数组的和int ans = nums.length + 1; // 初始化答案为一个不可能的大值（数组长度+1）// 遍历数组，右指针 right 表示子数组的结束位置for (int right = 0; right < nums.length; right++) {sum += nums[right]; // 向当前子数组的和中加入 nums[right]// 当当前子数组的和大于等于目标值时，尝试缩小子数组while (sum >= target) {sum -= nums[left]; // 从和中去掉子数组的第一个元素ans = Math.min(ans, right - left + 1); // 更新最小子数组长度left++; // 左指针向右移动，减小子数组的长度}}// 检查是否找到了符合条件的子数组if (ans == nums.length + 1) {return 0; // 如果 ans 仍然是初始化的值，说明没有找到符合条件的子数组，返回 0} else {return ans; // 否则返回找到的最短子数组长度}}
}
3. 无重复字符的最长子串
中等
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
class Solution {public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>(); // 使用一个HashSet来记录每个字符是否出现过char[] ch = s.toCharArray(); // 将输入的字符串转换为字符数组，便于索引操作int left = 0; // 左指针，用于表示当前考察的子串的开始位置int count = 0; // 当前窗口的长度int ans = 0; // 用于记录遇到的最长无重复字符子串的长度// 遍历字符串中的每个字符for (int right = 0; right < ch.length; right++) {if (!set.contains(ch[right])) { // 如果当前字符不在HashSet中，说明未重复set.add(ch[right]); // 将此字符加入HashSetcount = count + 1; // 窗口长度增加ans = Math.max(ans, count); // 更新最大长度} else { // 如果当前字符已在HashSet中，说明重复了// 移动左指针，直到移除重复的字符while (set.contains(ch[right])) {set.remove(ch[left]); // 移除左指针处的字符left++; // 左指针向右移动count--; // 窗口长度减少}set.add(ch[right]); // 将当前字符加入HashSetcount++; // 窗口长度增加}}return ans; // 返回最长无重复字符子串的长度}
}
class Solution {public int lengthOfLongestSubstring(String s) {int[] ch = new int[128];for(int i=0;i<128;i++){ch[i]=-1;}int ans=0;int st=0;for(int i=0;i<s.length();i++){int c = s.charAt(i);if(ch[c]!=-1){st=Math.max(st,ch[c]);}ans=Math.max(ans,i-st+1);ch[c]=i+1;}return ans;}
}904. 水果成篮
中等
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。
class Solution {public int totalFruit(int[] fruits) {int left = 0; // 初始化左指针，表示当前子数组的开始位置int right = 0; // 初始化右指针，表示当前子数组的结束位置int resault = 0; // 用于存储最长子数组的长度Map<Integer,Integer> map = new HashMap<>(); // 哈希表用于存储窗口内各种水果的数量// 遍历所有水果for(right = 0; right < fruits.length; right++){// 将当前水果加入到哈希表中，计数加1map.put(fruits[right] , map.getOrDefault(fruits[right] , 0) + 1);// 当哈希表中的水果种类超过2种时，缩小窗口while(map.size() > 2){// 将左指针所在的水果计数减1map.put(fruits[left], map.get(fruits[left]) - 1);// 如果某种水果的数量减到0，从哈希表中移除if(map.get(fruits[left]) == 0){map.remove(fruits[left]);}// 左指针向右移动，缩小窗口left++;}// 更新最大子数组的长度resault = Math.max(resault, right - left + 1);}return resault; // 返回最大长度}
}
76. 最小覆盖子串
困难
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
class Solution {public String minWindow(String s, String t) {// 边界条件检查if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {return ""; // 如果输入不合理，则返回空字符串}int[] map = new int[128]; // ASCII字符映射表，用于记录字符串t中各字符的数量int count = t.length(); // 需要匹配的字符总数int start = 0, end = 0; // 滑动窗口的起始和结束位置int minLen = Integer.MAX_VALUE; // 最小窗口长度，初始化为最大整数值int startIndex = 0; // 最小窗口的起始索引// 遍历字符串t，初始化字符计数器for (char c : t.toCharArray()) {map[c]++; // 增加t中字符的计数}char[] chS = s.toCharArray(); // 将字符串s转换为字符数组，以便操作// 扩展窗口的右边界while (end < chS.length) {// 当前字符在t中，减少相应的计数，并扩展窗口的右边界if (map[chS[end++]]-- > 0) {count--; // 减少需要匹配的字符计数}// 当所有字符都匹配后while (count == 0) {// 如果当前窗口的长度小于已记录的最小长度，则更新最小窗口if (end - start < minLen) {startIndex = start; // 更新最小窗口起始索引minLen = end - start; // 更新最小窗口长度}// 尝试收缩窗口的左边界，同时更新字符计数器和匹配计数if (map[chS[start++]]++ == 0) {count++; // 如果移除的字符是需要的字符，则增加需要匹配的字符计数}}}// 如果没有找到有效的窗口，则返回空字符串，否则返回最小窗口子字符串return minLen == Integer.MAX_VALUE ? "" : new String(chS, startIndex, minLen);}
}
438. 找到字符串中所有字母异位词
中等
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
class Solution {public List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length(); // s和p的长度if (sLen < pLen) {return new ArrayList<Integer>(); // 如果s的长度小于p的长度，直接返回空列表}List<Integer> ans = new ArrayList<Integer>(); // 存储所有异位词起始索引的列表int[] sCount = new int[26]; // s中的字符计数int[] pCount = new int[26]; // p中的字符计数// 初始化计数数组for (int i = 0; i < pLen; ++i) {++sCount[s.charAt(i) - 'a']; // 对s的前pLen个字符进行计数++pCount[p.charAt(i) - 'a']; // 对p的所有字符进行计数}// 如果初始化时s的前pLen个字符的计数与p的字符计数相同，说明找到一个异位词if (Arrays.equals(sCount, pCount)) {ans.add(0); // 将起始索引0添加到结果列表中}// 遍历s中的每个字符，使用滑动窗口更新字符计数for (int i = 0; i < sLen - pLen; ++i) {--sCount[s.charAt(i) - 'a']; // 移除窗口最左侧的字符计数++sCount[s.charAt(i + pLen) - 'a']; // 添加窗口最右侧的新字符计数// 比较更新后的s计数和p计数是否相同，相同则为异位词if (Arrays.equals(sCount, pCount)) {ans.add(i + 1); // 将当前异位词的起始索引添加到结果列表中}}return ans; // 返回包含所有异位词起始索引的列表}
}
560. 和为 K 的子数组
中等
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
public class Solution {public int subarraySum(int[] nums, int k) {int count = 0; // 用于计算和为k的子数组数量int pre = 0; // 用于累加前缀和HashMap<Integer, Integer> mp = new HashMap<>(); // 哈希表用来存储前缀和及其出现的次数mp.put(0, 1); // 初始化，对于前缀和为0的情况，假设已经出现一次（处理边界情况，如数组的部分元素和正好为k）for (int i = 0; i < nums.length; i++) {pre += nums[i]; // 累加当前元素到前缀和中// 如果当前前缀和减去k的结果已存在于哈希表中，说明存在一个子数组的和为kif (mp.containsKey(pre - k)) {count += mp.get(pre - k); // 将这些子数组的数量加到count上}// 更新当前前缀和的计数，如果这个前缀和第一次出现，则初始化为1，否则累加mp.put(pre, mp.getOrDefault(pre, 0) + 1);}return count; // 返回所有满足条件的子数组数量}
}
239. Sliding Window Maximum
Hard
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int len = nums.length; // 数组的长度int[] res = new int[len - k + 1]; // 存储每个窗口的最大值int left = 0; // 窗口的左边界int right = k - 1; // 窗口的右边界int max = Integer.MIN_VALUE; // 当前窗口中的最大值int maxIndex = -1; // 当前最大值的索引// 遍历数组，直到右边界达到数组的末尾while (right < len) {// 如果最大值的索引仍在窗口内if (left <= maxIndex) {// 检查新加入窗口的元素是否大于当前最大值if (nums[right] >= nums[maxIndex]) {maxIndex = right; // 更新最大值索引max = nums[right]; // 更新最大值}// 否则，重新计算当前窗口的最大值} else if (nums[right] >= max - 1 ) {maxIndex = right;max = nums[right];} else if (nums[left] >= max - 1 ) {maxIndex = left;max = nums[left];} else {max = nums[left];// 遍历当前窗口，找出最大值和对应的索引for (int j = left + 1; j <= right; j++) {if (nums[j] >= max) {maxIndex = j;max = nums[j];}}}// 将当前窗口的最大值存入结果数组res[left] = max;// 窗口向右移动left++;right++;}return res; // 返回结果数组}
}
这篇关于Sliding Windows的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
