不定长滑动窗口

无重复字符的最长子串如何求解？

• 用哈希表统计窗口内字符出现次数;
• right 每轮加入一个字符;
• 窗口出现重复字符时, 循环右移 left 并减少对应计数, 直到窗口恢复无重复;
• 恢复合法后用窗口长度更新最大值;

function lengthOfLongestSubstring(s: string): number {
  const count: Record<string, number> = {};
  let left = 0;
  let right = 0;
  let res = 0;
  while (right < s.length) {
    count[s[right]] = (count[s[right]] ?? 0) + 1;
    while (count[s[right]] > 1) {
      count[s[left]]--;
      left++;
    }
    res = Math.max(res, right - left + 1);
    right++;
  }
  return res;
}

• 时间复杂度: O(n); 空间复杂度: O(字符集大小);

如何求和大于等于目标值的最短子数组？

• right 扩张并累加和, 只要 sum >= target 就更新最短长度, 再右移 left 收缩;
• 用 nums.length + 1 作哨兵值标记未找到;

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0;
  let right = 0;
  let sum = 0;
  let res = nums.length + 1;
  while (right < nums.length) {
    sum += nums[right];
    while (sum >= target) {
      res = Math.min(res, right - left + 1);
      sum -= nums[left];
      left++;
    }
    right++;
  }
  return res === nums.length + 1 ? 0 : res;
}

如何统计乘积小于 k 的子数组数目？

• right 扩张后把乘积除以 left 直到小于 k;
• 合法窗口内以 right 结尾的子数组共有 right - left + 1 个, 一次累加;
• 边界: k <= 1 时乘积不可能更小, 直接返回 0;

function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k <= 1) return 0;
  let left = 0;
  let right = 0;
  let product = 1;
  let res = 0;
  while (right < nums.length) {
    product *= nums[right];
    while (product >= k) {
      product /= nums[left];
      left++;
    }
    res += right - left + 1;
    right++;
  }
  return res;
}

如何求最多替换 k 个 0 后的最长连续 1？

• 统计窗口内 0 的个数 zero;
• zero 大于 k 时右移 left 直到重新合法;
• 合法时用窗口长度更新最大值;

function longestOnes(nums: number[], k: number): number {
  let left = 0;
  let right = 0;
  let zero = 0;
  let max = 0;
  while (right < nums.length) {
    if (nums[right] === 0) zero++;
    while (zero > k) {
      if (nums[left] === 0) zero--;
      left++;
    }
    max = Math.max(max, right - left + 1);
    right++;
  }
  return max;
}

• 上述三题的时间复杂度均为 O(n), 空间复杂度为 O(1);