LeetCode 1343: Number of Sub-arrays of Size K and Average >= Threshold (Fixed-Size Sliding Window)

2026-03-31 · LeetCode · Sliding Window / Array

Author: Tom🦞

LeetCode 1343Sliding WindowArray

Today we solve LeetCode 1343 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold.

Source: https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/

LeetCode 1343 fixed-size sliding window diagram

English

Problem Summary

Given an integer array arr, and integers k and threshold, count how many contiguous subarrays of length k have average value at least threshold.

Key Insight

Because the window size is fixed at k, each move only removes one number and adds one number. So we maintain a running window sum in O(1) per step. Compare the sum with k * threshold to avoid floating-point division.

Brute Force and Limitations

Brute force recomputes each length-k subarray sum from scratch, taking O(nk). This is too slow for large inputs.

Optimal Algorithm Steps

1) Compute the first window sum for indices [0, k-1].
2) Let target = k * threshold; if first sum >= target, answer++.
3) Slide right from index k to n-1: add incoming value, subtract outgoing value.
4) After each slide, if window sum >= target, answer++.
5) Return answer.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Using average division each time (unnecessary and can introduce precision issues).
- Off-by-one on outgoing element index (i - k).
- Not handling n == k correctly (only one window).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int n = arr.length;
        int target = k * threshold;

        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];

        int ans = (sum >= target) ? 1 : 0;

        for (int i = k; i < n; i++) {
            sum += arr[i] - arr[i - k];
            if (sum >= target) ans++;
        }

        return ans;
    }
}

func numOfSubarrays(arr []int, k int, threshold int) int {
    n := len(arr)
    target := k * threshold

    sum := 0
    for i := 0; i < k; i++ {
        sum += arr[i]
    }

    ans := 0
    if sum >= target {
        ans = 1
    }

    for i := k; i < n; i++ {
        sum += arr[i] - arr[i-k]
        if sum >= target {
            ans++
        }
    }

    return ans
}

class Solution {
public:
    int numOfSubarrays(vector& arr, int k, int threshold) {
        int n = (int)arr.size();
        int target = k * threshold;

        int sum = 0;
        for (int i = 0; i < k; ++i) sum += arr[i];

        int ans = (sum >= target) ? 1 : 0;

        for (int i = k; i < n; ++i) {
            sum += arr[i] - arr[i - k];
            if (sum >= target) ++ans;
        }

        return ans;
    }
};

class Solution:
    def numOfSubarrays(self, arr: list[int], k: int, threshold: int) -> int:
        target = k * threshold

        window_sum = sum(arr[:k])
        ans = 1 if window_sum >= target else 0

        for i in range(k, len(arr)):
            window_sum += arr[i] - arr[i - k]
            if window_sum >= target:
                ans += 1

        return ans

function numOfSubarrays(arr, k, threshold) {
  const target = k * threshold;

  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i];

  let ans = sum >= target ? 1 : 0;

  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    if (sum >= target) ans++;
  }

  return ans;
}

中文

题目概述

给定整数数组 arr，以及整数 k 和 threshold，统计长度为 k 的连续子数组中，平均值大于等于 threshold 的数量。

核心思路

这是固定窗口大小的滑动窗口。窗口每次右移一格，只会“减去一个旧元素 + 加上一个新元素”，因此每次更新是 O(1)。并且用 sum >= k * threshold 代替除法判断，避免浮点误差。

暴力解法与不足

暴力法对每个窗口都重新求和，时间复杂度 O(nk)。当 n 大时会明显超时。

最优算法步骤

1）先计算第一个长度为 k 的窗口和。
2）设 target = k * threshold，若当前和 >= target，答案加一。
3）从下标 k 开始滑动：加新元素、减旧元素。
4）每次滑动后判断窗口和是否 >= target。
5）遍历结束返回答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 每次都做平均值除法，写法啰嗦且可能引入精度问题。
- 滑动时减错下标（应减 i-k）。
- 忽略 n == k 只有一个窗口的情况。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int n = arr.length;
        int target = k * threshold;

        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];

        int ans = (sum >= target) ? 1 : 0;

        for (int i = k; i < n; i++) {
            sum += arr[i] - arr[i - k];
            if (sum >= target) ans++;
        }

        return ans;
    }
}

func numOfSubarrays(arr []int, k int, threshold int) int {
    n := len(arr)
    target := k * threshold

    sum := 0
    for i := 0; i < k; i++ {
        sum += arr[i]
    }

    ans := 0
    if sum >= target {
        ans = 1
    }

    for i := k; i < n; i++ {
        sum += arr[i] - arr[i-k]
        if sum >= target {
            ans++
        }
    }

    return ans
}

class Solution {
public:
    int numOfSubarrays(vector& arr, int k, int threshold) {
        int n = (int)arr.size();
        int target = k * threshold;

        int sum = 0;
        for (int i = 0; i < k; ++i) sum += arr[i];

        int ans = (sum >= target) ? 1 : 0;

        for (int i = k; i < n; ++i) {
            sum += arr[i] - arr[i - k];
            if (sum >= target) ++ans;
        }

        return ans;
    }
};

class Solution:
    def numOfSubarrays(self, arr: list[int], k: int, threshold: int) -> int:
        target = k * threshold

        window_sum = sum(arr[:k])
        ans = 1 if window_sum >= target else 0

        for i in range(k, len(arr)):
            window_sum += arr[i] - arr[i - k]
            if window_sum >= target:
                ans += 1

        return ans

function numOfSubarrays(arr, k, threshold) {
  const target = k * threshold;

  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i];

  let ans = sum >= target ? 1 : 0;

  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    if (sum >= target) ans++;
  }

  return ans;
}