publicint[] template01(int[] nums, int k) { int ans = 0; int sum = 0; int maxSum = 0; for (int i = 0; i < nums.length; i++) { // 更新当前窗口内的累加和 sum += nums[i]; // 第一次满足该条件时，[0,i] 区间形成了第一个窗口 // 此时就该记录该区间内的数字和的 // 之后i不断++，窗口的右边界不断右移，左边界 i-k+1 也不断右移 if (i >= k - 1) { if (sum > maxSum) { maxSum = sum; ans = i - k + 1; } // 窗口即将整体右移，更新sum：减去左边界的值 sum -= nums[i - k + 1]; } } }
publicintlengthOfLongestSubstring(String s){ if (s == null || s.length() < 1) { return0; } return lengthOfLongestSubstring01(s); }
// 滑动窗口 publicintlengthOfLongestSubstring01(String s){ int left = 0; int right = 0; // 词频表 Map<Character, Integer> freq = new HashMap<>(); int maxCount = 0;
publicintminSubArrayLen(int target, int[] nums){ if (nums == null || nums.length == 0) { return0; } int left = 0; int right = 0; int minLength = Integer.MAX_VALUE; int sum = 0; // 外层更新 right while (right < nums.length) { // 首先将当前 right 的值计算到指标内 sum += nums[right]; right++; // 内层循环不断移动 left 直到满足条件后退出 // 一直遍历直到left移动到[left, right-1]的sum值小于target while (sum >= target) { minLength = Math.min(minLength, right - left); sum -= nums[left]; left++; } } return minLength == Integer.MAX_VALUE ? 0 : minLength; }
最小覆盖子串
76. 最小覆盖子串：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
// 先准备一个词频表 int[] map = newint[256]; // 记录“欠的总债” int all = t.length(); for (char cur : tchar) { // 每个字符的词频加一，即先记录下来“欠的债” // 将在后面被不断还债 map[cur]++; }
// 用于记录待返回的答案 int minLength = Integer.MAX_VALUE; int ansl = -1; int ansr = -1;
// [left, right)：左闭右开，left == right 时代表区间内没有元素 int left = 0; int right = 0;
// right 右移的过程，是在不断“还债”，词频表里的当前字符的频率值不断减少 // left 右移的过程，是在不断“欠债”，词频表里的当前字符的频率值不断增加 // right 在到达 s 字符串的末尾前一直循环 while (right < s.length()) { // 先把当前 right 位置的词频减一（还一次债） map[schar[right]]--;
// 判断减一后的词频是否大于等于0 if (map[schar[right]] >= 0) { // 如果当前字符在还了一次债后还是大于等于0， // 说明当前还债是一次有效还债，总债数 all 需要减一 all--; } // 当 right 到了某个位置后满足 all == 0 的条件时，说明找到了一个局部子串 // 但是该区间不一定是最短的，因此 left 该开始右移了 // 开始不断右移 left，直到某个位置的 left 与 right 一起构成局部最小子串 if (all == 0) { // 当前字符的词频不断增加，直到其重新等于0（该过程就是在不断欠债） // 目的是让之前词频小于0的字符的词频重新回到0。 // 这些字符在之前还债时词频不断--，小于了0（可以理解为多还了这些债，是一种浪费，导致子串变长），那些词频等于0的就是没有多还债的，不是浪费，需要保留的 // 注意，在这个过程中，是一直满足 all == 0 的，不会令任意一个词频大于 0 的 // 因为一旦词频等于了0，就退出了 while 循环 // 当前位置词频小于0，说明 left 能往右移动 while (map[schar[left]] < 0) { map[schar[left++]]++; } // 跳出 while 循环的时机是，left 来到了一个出现在 s 中的字符， // 这个字符当前的词频等于0，说明不能再欠债了，否则其词频就大于0了，all就大于0了 // [left,right] 的位置就是局部的最小子串 // 解释肯定是在 s 中的字符的原因：因为不在 s 中的字符，其词频上限就是0。 // 一旦这些字符在前面有还债，那么其对应的词频肯定小于0，不可能会等于0， // 因此这里等于0的肯定是那些在 s 中的字符，其在left右移欠债的过程中，使得其词频从负转为0， // 因此此时就不能再右移left了，否则all就会大于0了，就不是最小子串了。我们要保证整个过程中 all 一直等于0 // 保存该值 if (minLength > (right - left + 1)) { minLength = right - left + 1; ansl = left; ansr = right; } // 找到了一个局部最小子串后，left 需要继续右移，开始寻找新的局部子串 // 人为增加一个all，为了是让 right 继续向右寻找新的局部子串 all++; map[schar[left++]]++; } // left 此时已经调整到了局部最小子串的位置，接下来继续移动 right，进行新的“还债”过程 right++; } // 注意 substring 方法是左闭右开的 [ansl, ansr + 1)，所以 ansr 要加一 return minLength == Integer.MAX_VALUE ? "" : s.substring(ansl, ansr + 1); }
K 个不同整数的子数组
992. K 个不同整数的子数组：给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。返回 A 中好子数组的数目。
// [left, right)：左闭右开的范围内存储着符合题意的“最多有K个不同整数”的子数组 int left = 0; int right = 0; // 记录当前子数组[left, right)中，存在的不同整数的种类数 // 当该种类数大于K时，说明不符合题目中最多有K个的条件，此时就需要left++ int kinds = 0; // 记录返回结果 int res = 0;
publicstaticint[] getMaxWindow(int[] nums, int w) { if (nums == null || nums.length < w || w < 1) { returnnull; }
Deque<Integer> queueMax = new LinkedList<>(); // 先创建出来第一个窗口 for (int i = 0; i < w; i++) { // 如果队尾元素小于等于当前元素，则队尾元素弹出（代表该元素不可能为当前窗口内的最大值了，直接丢弃） if (!queueMax.isEmpty() && nums[queueMax.peekLast()] <= nums[i]) { queueMax.pollLast(); } // 直到队尾元素大于当前元素时停止弹出，将当前元素的索引加入队列 // 注意要加入的是索引而不是值 queueMax.addLast(i); }
// 初始化两个指针位置，一个在0位置，一个在w-1位置 int left = 0; int right = w - 1; // 要返回的数组的长度是 nums.length - w + 1，注意不要忘了加一 int[] res = newint[nums.length - w + 1];
// right 一直遍历到数组尾部 while (right < nums.length) { // left 指向当前位置索引 // 先将队列中的队首元素添加到res中，其就是当前窗口内的最大值 // 注意不能弹出，只是获取该值。要在该元素过期时才弹出 res[left++] = nums[queueMax.peekFirst()];
// 此时的 left -1 就是已经过期的元素，需要弹出 if (left - 1 == queueMax.peekFirst()) { queueMax.pollFirst(); }
// 若成立，则说明窗口走到尽头了，不能再往下继续right++了，要越界了，直接break; if (left == nums.length - (w - 1)) { break; }
// 此时 left 已经右移了一位，窗口需要整体右移，因此该 right 右移了 right++; // right 右移时，需要将新的 right 加入到队列中，更新窗口内的最大值 // 注意相等的情况也是要移出队列的，因为之前的元素是旧的，现在来的是新的 while (!queueMax.isEmpty() && nums[queueMax.peekLast()] <= nums[right]) { queueMax.pollLast(); } queueMax.addLast(right); }
return res; }
publicstaticint[] getMaxWindow1(int[] arr, int w) { if (arr == null || w < 1 || arr.length < w) { returnnull; } LinkedList<Integer> qmax = new LinkedList<Integer>(); int[] res = newint[arr.length - w + 1]; int index = 0; for (int i = 0; i < arr.length; i++) { // 窗口的 R while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) { qmax.pollLast(); } qmax.addLast(i); if (qmax.peekFirst() == i - w) { // i-w ：过期的下标 qmax.pollFirst(); // 这里的i-w已经是过期了的，不在当前窗口里的了 } if (i >= w - 1) { // 窗口形成了 i 从 W-1 开始，窗口已经形成了 res[index++] = arr[qmax.peekFirst()]; } } return res; }
// for test publicstaticvoidprintArray(int[] arr){ for (int i = 0; i != arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); }
