定长滑动窗口

定长窗口如何维护窗口内的和或乘积？

• 用 right 扩张窗口并累加当前元素;
• 窗口长度首次达到 k 时判定一次, 然后减去 left 处元素并右移 left;
• 之后每轮都是"进一个出一个", 窗口长度保持 k;

长度固定且平均值不小于阈值的子数组如何计数？

• 判定条件: 窗口和 sum >= threshold * k, 避免做浮点除法;
• 满足即把计数加一;

function numOfSubarrays(arr: number[], k: number, threshold: number): number {
  let left = 0;
  let right = 0;
  let sum = 0;
  let ans = 0;
  while (right < arr.length) {
    sum += arr[right];
    if (right - left + 1 === k) {
      if (sum >= threshold * k) ans++;
      sum -= arr[left];
      left++;
    }
    right++;
  }
  return ans;
}

定长滑动窗口的复杂度是多少？

• 时间复杂度: O(n), 每个元素进出窗口各一次;
• 空间复杂度: O(1), 只需维护窗口和;