企业官网建设流程全解析

滑动窗口模板：

int left = 0, right = 0;
int valid = 0;
// 各类辅助变量：如最短长度 minLen、最长长度 maxLen、起始位置 start...

while (right < n) {
char c = s[right];
right++;
// 【1. 扩大窗口】：更新 window 频次、valid 状态

// 【2. 判断收缩】：这里的条件视题目而定
// 求最短 (76题)：while (valid == needSize) → 满足条件就缩
// 求最长 (3题)： while (window[c] > 1) → 不满足条件就缩
// 定长求异位词 (438题)：while (right - left == p.length()) → 长度到了就缩
while (窗口需要收缩) {

// 【3. 更新答案】：求最短在这里更新（因为目前是合法状态）
// ...

char d = s[left];
left++;
// 【4. 缩小窗口】：更新 window 频次、valid 状态
}

// 【注意】：如果是求最长 (LC 3)，答案在 while 循环外面更新（因为缩完之后才是合法的最大窗口）
}

560. 和为 K 的子数组 - 力扣（LeetCode）

不用滑动窗口，因为有负数

前缀和 + 哈希表，和两数之和类似，存一个map，记录每种前缀和的次数，如果map存在presunm[i]-k就加上对应的value。

class Solution { public int subarraySum(int[] nums, int k) { int presum=0; int res=0; HashMap<Integer, Integer> count=new HashMap<>(); count.put(0,1); for(int i=0;i<nums.length;i++){ presum+=nums[i]; if(count.containsKey(presum-k)){ res+=count.get(presum-k); } count.put(presum, count.getOrDefault(presum, 0)+1); } return res; } }

76. 最小覆盖子串 - 力扣（LeetCode）

滑动窗口，

1. 状态判定：以need和window频次数组为基准，用valid记录“已达标字符种类数”来代替遍历比对。
2. 状态维护：右指针进窗、左指针出窗时，必须同步对称地更新窗口频次，并精准控制valid的加减。

class Solution { public String minWindow(String s, String t) { // 1. 特判：如果 s 比 t 还短，绝对不可能包含 t，直接返回空串 if (s.length() < t.length()) { return ""; } // window 数组：记录当前滑动窗口中，每个字符出现的实际次数 int[] window = new int[128]; // need 数组：记录目标字符串 t 中，每个字符需要的次数 int[] need = new int[128]; int needSize = 0; // 记录 t 中有多少种【不同】的字符 // 2. 统计 t 的字符信息 for (int i = 0; i < t.length(); i++) { char c = t.charAt(i); // 如果是第一次遇到这个字符，说明发现新种类了 if (need[c] == 0) { needSize++; } need[c]++; } int left = 0; // 滑动窗口的左边界 int start = 0; // 记录最终最小覆盖子串的起始下标 int minLen = Integer.MAX_VALUE; // 记录最小覆盖子串的长度，初始为无穷大 int valid = 0; // 记录当前窗口内，有多少【种】字符的数量已经达标了 // 3. 开始遍历 s，right 是滑动窗口的右边界 for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // ================= 进窗操作 ================= window[c]++; // 当前字符进入窗口，频次 +1 // 如果这个字符是 t 需要的，判断是否【刚好】凑齐 if (need[c] > 0 && window[c] == need[c]) { valid++; // 刚好达标，达标种类 +1 } // ================= 缩窗操作 ================= // 当 valid == needSize 时，说明当前窗口已经完全覆盖了 t // 这是一个合法的窗口，我们要尝试把左边界往右缩，看看能不能找到更短的 while (valid == needSize) { // 4. 更新最优解：如果当前窗口长度比之前记录的还短，就更新 if (right - left + 1 < minLen) { start = left; minLen = right - left + 1; } // 5. 准备将最左边的字符移出窗口 char remove = s.charAt(left); left++; // 左边界向右移动 // 如果移出的是 t 需要的字符 if (need[remove] > 0) { // 【关键点】：如果移出前，它的数量刚好等于 t 需要的数量 // 说明移出后它就不够了，达标种类要减 1 if (window[remove] == need[remove]) { valid--; } // 无论是否达标，窗口里的实际数量必须减 1 window[remove]--; } } // 退出 while 循环说明 valid < needSize，窗口不合法了，right 继续往右扩 } // 6. 返回结果：如果 minLen 没被更新过，说明没找到，返回空串；否则截取最小子串 return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen); } }

239. 滑动窗口最大值 - 力扣（LeetCode）

滑动窗口+单调队列，时间复杂度n

一种不优雅的写法，能通过，每次删除left

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> queue=new LinkedList<>(); int left=0; int []res=new int[nums.length-k+1]; int idx=0; for(int right=0;right<nums.length;right++){ while(queue.size()>0&& nums[queue.peekLast()]<nums[right]){ queue.pollLast(); } queue.offerLast(right); if(right-left+1==k){ res[idx++]=nums[queue.peekFirst()]; queue.remove(left); left++; } } return res; } }

清理队头的逻辑变了，left（窗口左边界）永远一定小于等于queue.peekFirst()（队头元素的下标），当窗口向右滑动，左边界left移动时，会发生以下三种情况：

1. left < queue.peekFirst()：left被入队时候清理过了

2. left == queue.peekFirst()相等的时候，说明left的位置一直是最大值，没有被入队清理，如果再往右滑一步，它就过期了。所以在记录完当前窗口的最大值后，必须立刻pollFirst()把它请出去。

3. left > queue.peekFirst，不存在，因为队列元素就在窗口内

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> queue=new LinkedList<>(); int left=0; int []res=new int[nums.length-k+1]; int idx=0; for(int right=0;right<nums.length;right++){ while(queue.size()>0&& nums[queue.peekLast()]<nums[right]){ queue.pollLast(); } queue.offerLast(right); if(right-left+1==k){ res[idx++]=nums[queue.peekFirst()]; if (queue.peekFirst() == left) { queue.pollFirst(); } left++; } } return res; } }