模板

public static int slideWindow(int[] nums,int k) { // Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表) int x, y = …, …; // Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口 int start = 0; for (int i = 0; i < nums.length; i++) { // Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度) x = new_x if (condition) y = new_y } / ——————- 下面是两种情况，读者请根据题意二选1 ——————- / // Step 4 - 情况1 // 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 // 如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, // 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 if (窗口长度达到了限定长度){ // 更新 (部分或所有) 维护变量 // 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变 } return … // Step 4 - 情况2 // 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题 // 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法 // 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 if(合法){ // 更新维护变量 } while (不合法){ // 更新(部分或所有) 维护变量 // 不断移动窗口左指针直到窗口再次合法 } // Step 5: 返回答案 return … }

实战 无重复字符的最大子串

:::info 输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 :::

  1. public int lengthOfLongestSubstring(String s) {
  2.     Map<Character, Integer> map = new HashMap<>();
  3.     int l = 0, max = 0;
  4.     for (int i = 0; i < s.length(); i++) {
  5.         char c = s.charAt(i);
  6.         map.put(c, map.getOrDefault(c, 0) + 1);
  7.         while (map.get(c) > 1) { // while(不合法) 左指针移动更新到合法
  8.             char lc = s.charAt(l);
  9.             map.put(c, map.getOrDefault(lc, 0) - 1);
  10.             if (map.get(lc) == 0) {
  11.                 map.remove(lc);
  12.             }
  13.             l++;
  14.         }
  15.         max = Math.max(max, i - l + 1);// 合法的状态下更新最大值
  16.     }
  17.     return max;
  18. }

细节关注：

  1. 和字符个数有关的话常用两个map相等判断，注意getOrDefault合法加个数，不合法减个数，为0的话删除key
  2. 注意while减窗口的时候更新维护变量是合法的时候维护还是不合法的时候更新维护变量
  3. 滑动窗口适用于连续子数组，且子数组起点不一定是0，主要是优化了O(n2)的时间复杂度