LeetCode 1343 题解滑动窗口与前缀和——求解「大小 k 且平均值 ≥ 阈值的子数组」数量【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 1343「Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold大小为 K 且平均值大于等于阈值的子数组数目」展开系统讲解暴力枚举、前缀和与两种滑动窗口共四套解法并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整可运行实现。读完本文你将掌握「固定长度窗口」类问题从 O(n·k) 暴力到 O(n) 滑窗的完整优化链路理解前缀和与滑动窗口的适用边界以及整数除法截断等常见陷阱的规避方法。本文内容以仓库文档 articles/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.md 为骨架展开所有多语言实现均可在本仓库各语言目录下找到对应编号文件如 python/1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.py、java/1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.java 等。前置知识在动手解题之前需要先具备以下三项基本功滑动窗口Sliding Window高效处理定长子数组的核心技巧通过在窗口边界添加/移除元素来维护一个持续更新的窗口状态避免重复扫描。前缀和Prefix Sum预先计算累计和数组使任意区间[l, r]的区间和查询降为 O(1)。数组遍历Array Traversal使用多个指针界定窗口边界理解左右指针的移动语义。这三项前置技能恰好也是本仓库大量数组类题目的通用基石例如 maximum-average-subarray-ii.md、subarray-sum-equals-k.md 等文章同样依赖它们。问题定义给定一个整数数组arr、窗口大小k与阈值threshold要求统计所有长度为 k的连续子数组中满足「子数组平均值 ≥ threshold」的子数组数量。输入arr整数数组、k窗口长度、threshold平均值阈值输出满足条件的子数组数目整数判定条件sum(arr[l..lk-1]) / k threshold以本题的数据规模来看数组长度可达 10^5 量级O(n·k) 的暴力做法在大数据上会退化得不可接受因此前缀和与滑动窗口的 O(n) 解法才是重点。解法一暴力枚举Brute Force直觉对每个合法的子数组起点l取值范围0到n - k从头重新累加该窗口内所有元素得到sum再判断sum / k是否达到阈值。窗口之间没有信息复用每个窗口都独立重算。算法步骤遍历所有可能的起始下标l范围是0到n - k对每个窗口计算从l到l k - 1的元素之和若sum / k threshold结果计数器res自增返回res。多语言实现class Solution: def numOfSubarrays(self, arr: List[int], k: int, threshold: int) - int: res 0 l 0 for r in range(k - 1, len(arr)): sum_ 0 for i in range(l, r 1): sum_ arr[i] if sum_ / k threshold: res 1 l 1 return respublic class Solution { public int numOfSubarrays(int[] arr, int k, int threshold) { int res 0, l 0; for (int r k - 1; r arr.length; r) { int sum 0; for (int i l; i r; i) { sum arr[i]; } if (sum / k threshold) { res; } l; } return res; } }class Solution { public: int numOfSubarrays(vectorint arr, int k, int threshold) { int res 0, l 0; for (int r k - 1; r arr.size(); r) { int sum 0; for (int i l; i r; i) { sum arr[i]; } if (sum / k threshold) { res; } l; } return res; } };class Solution { /** * param {number[]} arr * param {number} k * param {number} threshold * return {number} */ numOfSubarrays(arr, k, threshold) { let res 0, l 0; for (let r k - 1; r arr.length; r) { let sum 0; for (let i l; i r; i) { sum arr[i]; } if (sum / k threshold) { res; } l; } return res; } }public class Solution { public int NumOfSubarrays(int[] arr, int k, int threshold) { int res 0; int l 0; for (int r k - 1; r arr.Length; r) { int sum 0; for (int i l; i r; i) { sum arr[i]; } if (sum / k threshold) { res; } l; } return res; } }func numOfSubarrays(arr []int, k int, threshold int) int { res : 0 l : 0 for r : k - 1; r len(arr); r { sum : 0 for i : l; i r; i { sum arr[i] } if sum/k threshold { res } l } return res }class Solution { fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int { var res 0 var l 0 for (r in k - 1 until arr.size) { var sum 0 for (i in l..r) { sum arr[i] } if (sum / k threshold) { res } l } return res } }class Solution { func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) - Int { var res 0 var l 0 for r in (k - 1)..arr.count { var sum 0 for i in l...r { sum arr[i] } if sum / k threshold { res 1 } l 1 } return res } }impl Solution { pub fn num_of_subarrays(arr: Veci32, k: i32, threshold: i32) - i32 { let k k as usize; let mut res 0; let mut l 0; for r in (k - 1)..arr.len() { let mut sum 0; for i in l..r { sum arr[i]; } if sum / k as i32 threshold { res 1; } l 1; } res } }复杂度分析时间复杂度O(n · k)——外层遍历约 n 个起点内层每个窗口重新累加 k 个元素。空间复杂度O(1)——只使用常数个辅助变量。其中 n 为数组arr的长度k 为子数组长度。窗口之间毫无信息复用这是暴力法的根本症结。解法二前缀和Prefix Sum直觉暴力法的冗余在于每个窗口都从头累加。前缀和把「区间和」变成一次减法预处理出prefix[i]表示arr[0..i-1]的累计和之后任意[l, r]区间和即为prefix[r1] - prefix[l]。用 O(n) 的空间预处理换来 O(1) 的区间和查询。算法步骤构建前缀和数组prefix[i]保存arr从下标0到i-1的元素之和prefix长度为n1prefix[0] 0对每个长度为 k 的窗口用prefix[r1] - prefix[l]计算窗口和若平均值达到阈值计数器自增返回总数。多语言实现class Solution: def numOfSubarrays(self, arr: List[int], k: int, threshold: int) - int: prefix_sum [0] * (len(arr) 1) for i in range(len(arr)): prefix_sum[i 1] prefix_sum[i] arr[i] res l 0 for r in range(k - 1, len(arr)): sum_ prefix_sum[r 1] - prefix_sum[l] if sum_ / k threshold: res 1 l 1 return respublic class Solution { public int numOfSubarrays(int[] arr, int k, int threshold) { int[] prefixSum new int[arr.length 1]; for (int i 0; i arr.length; i) { prefixSum[i 1] prefixSum[i] arr[i]; } int res 0, l 0; for (int r k - 1; r arr.length; r) { int sum prefixSum[r 1] - prefixSum[l]; if (sum / k threshold) { res; } l; } return res; } }class Solution { public: int numOfSubarrays(vectorint arr, int k, int threshold) { vectorint prefixSum(arr.size() 1); for (int i 0; i arr.size(); i) { prefixSum[i 1] prefixSum[i] arr[i]; } int res 0, l 0; for (int r k - 1; r arr.size(); r) { int sum prefixSum[r 1] - prefixSum[l]; if (sum / k threshold) { res; } l; } return res; } };class Solution { /** * param {number[]} arr * param {number} k * param {number} threshold * return {number} */ numOfSubarrays(arr, k, threshold) { const prefixSum new Int32Array(arr.length 1); for (let i 0; i arr.length; i) { prefixSum[i 1] prefixSum[i] arr[i]; } let res 0, l 0; for (let r k - 1; r arr.length; r) { const sum prefixSum[r 1] - prefixSum[l]; if (sum / k threshold) { res; } l; } return res; } }public class Solution { public int NumOfSubarrays(int[] arr, int k, int threshold) { int[] prefixSum new int[arr.Length 1]; for (int i 0; i arr.Length; i) { prefixSum[i 1] prefixSum[i] arr[i]; } int res 0, l 0; for (int r k - 1; r arr.Length; r) { int sum prefixSum[r 1] - prefixSum[l]; if (sum / k threshold) { res; } l; } return res; } }func numOfSubarrays(arr []int, k int, threshold int) int { prefixSum : make([]int, len(arr)1) for i : 0; i len(arr); i { prefixSum[i1] prefixSum[i] arr[i] } res, l : 0, 0 for r : k - 1; r len(arr); r { sum : prefixSum[r1] - prefixSum[l] if sum/k threshold { res } l } return res }class Solution { fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int { val prefixSum IntArray(arr.size 1) for (i in arr.indices) { prefixSum[i 1] prefixSum[i] arr[i] } var res 0 var l 0 for (r in k - 1 until arr.size) { val sum prefixSum[r 1] - prefixSum[l] if (sum / k threshold) { res } l } return res } }class Solution { func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) - Int { var prefixSum Int for i in 0..arr.count { prefixSum[i 1] prefixSum[i] arr[i] } var res 0 var l 0 for r in (k - 1)..arr.count { let sum prefixSum[r 1] - prefixSum[l] if sum / k threshold { res 1 } l 1 } return res } }impl Solution { pub fn num_of_subarrays(arr: Veci32, k: i32, threshold: i32) - i32 { let k k as usize; let mut prefix_sum vec![0; arr.len() 1]; for i in 0..arr.len() { prefix_sum[i 1] prefix_sum[i] arr[i]; } let mut res 0; let mut l 0; for r in (k - 1)..arr.len() { let sum prefix_sum[r 1] - prefix_sum[l]; if sum / k as i32 threshold { res 1; } l 1; } res } }复杂度分析时间复杂度O(n)——一次 O(n) 预处理前缀和再加一次 O(n) 遍历窗口。空间复杂度O(n)——额外的前缀和数组占用 O(n) 空间。其中 n 为数组arr的长度k 为子数组长度。前缀和用「空间换时间」把区间和查询降为 O(1)但当问题只需要定长窗口时可以进一步省掉这份空间——这就是滑动窗口的用武之地。解法三滑动窗口 ISliding Window - I直觉维护一个「运行中的窗口和」curSum。窗口右移时只需加入新进入的右端元素、移除离开窗口的左端元素每次更新都是 O(1)彻底告别重复累加。同时不需要额外数组空间回到 O(1)。算法步骤用前k-1个元素初始化curSum对每个起始位置L加入位置L k - 1的元素凑满 k 个元素的完整窗口检查curSum / k是否达到阈值在进入下一个窗口前移除位置L的元素返回满足条件的子数组个数。多语言实现class Solution: def numOfSubarrays(self, arr: List[int], k: int, threshold: int) - int: res 0 curSum sum(arr[:k - 1]) for L in range(len(arr) - k 1): curSum arr[L k - 1] if (curSum / k) threshold: res 1 curSum - arr[L] return respublic class Solution { public int numOfSubarrays(int[] arr, int k, int threshold) { int res 0; int curSum 0; for (int i 0; i k - 1; i) { curSum arr[i]; } for (int L 0; L arr.length - k; L) { curSum arr[L k - 1]; if ((curSum / k) threshold) { res; } curSum - arr[L]; } return res; } }class Solution { public: int numOfSubarrays(vectorint arr, int k, int threshold) { int res 0, curSum 0; for (int i 0; i k - 1; i) { curSum arr[i]; } for (int L 0; L arr.size() - k; L) { curSum arr[L k - 1]; if ((curSum / k) threshold) { res; } curSum - arr[L]; } return res; } };class Solution { /** * param {number[]} arr * param {number} k * param {number} threshold * return {number} */ numOfSubarrays(arr, k, threshold) { let res 0; let curSum 0; for (let i 0; i k - 1; i) { curSum arr[i]; } for (let L 0; L arr.length - k; L) { curSum arr[L k - 1]; if (curSum / k threshold) { res; } curSum - arr[L]; } return res; } }public class Solution { public int NumOfSubarrays(int[] arr, int k, int threshold) { int res 0; int curSum 0; for (int i 0; i k - 1; i) { curSum arr[i]; } for (int L 0; L arr.Length - k; L) { curSum arr[L k - 1]; if (curSum / k threshold) { res; } curSum - arr[L]; } return res; } }func numOfSubarrays(arr []int, k int, threshold int) int { res : 0 curSum : 0 for i : 0; i k-1; i { curSum arr[i] } for L : 0; L len(arr)-k; L { curSum arr[Lk-1] if curSum/k threshold { res } curSum - arr[L] } return res }class Solution { fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int { var res 0 var curSum 0 for (i in 0 until k - 1) { curSum arr[i] } for (L in 0..arr.size - k) { curSum arr[L k - 1] if (curSum / k threshold) { res } curSum - arr[L] } return res } }class Solution { func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) - Int { var res 0 var curSum 0 for i in 0..(k - 1) { curSum arr[i] } for L in 0...(arr.count - k) { curSum arr[L k - 1] if curSum / k threshold { res 1 } curSum - arr[L] } return res } }impl Solution { pub fn num_of_subarrays(arr: Veci32, k: i32, threshold: i32) - i32 { let k k as usize; let mut res 0; let mut cur_sum 0; for i in 0..k - 1 { cur_sum arr[i]; } for l in 0..arr.len() - k { cur_sum arr[l k - 1]; if cur_sum / k as i32 threshold { res 1; } cur_sum - arr[l]; } res } }仓库源码对照本解法正是仓库中多数语言实现所选用的方案。例如 python/1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.py 与文档版本逐行一致cpp/1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.cpp 则采用「先求前 k 个元素之和、再用left/right双指针滑动」的等价写法注释中同样标注了T.C - O(N)、S.C - O(1)的复杂度结论。仓库中的实现风格还体现了语言的多样性JavaScript 版本javascript/1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.js通过R - L 1 k判断窗口是否凑满并在满窗时先判定再收缩go/1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.go 使用i - k 1定位被移除的最左元素。这些写法与文档给出的统一模板互为印证说明「先加右、判平均、再减左」是滑动窗口的通用骨架。复杂度分析时间复杂度O(n)——每个元素最多被加入一次、移除一次。空间复杂度O(1)额外空间——只维护一个运行中的curSum。其中 n 为数组arr的长度k 为子数组长度。解法四滑动窗口 IISliding Window - II直觉一个小而关键的优化与其每个窗口都做一次sum / k除法不如在循环开始前一次性把阈值乘以 k得到「目标窗口和」target threshold * k。此后每次只需比较curSum target把「平均值比较」转化为「整数和比较」既省去重复除法又从根本上规避了下一节要讲的整数除法截断问题。算法步骤将threshold乘以k得到目标窗口和右指针R从 0 开始逐步把新元素加入curSum当窗口长度达到 k即R k - 1时检查当前curSum是否达到或超过目标从窗口左侧移除最旧元素为下一个窗口腾出位置返回满足条件的子数组个数。多语言实现class Solution: def numOfSubarrays(self, arr: List[int], k: int, threshold: int) - int: threshold * k res curSum 0 for R in range(len(arr)): curSum arr[R] if R k - 1: res curSum threshold curSum - arr[R - k 1] return respublic class Solution { public int numOfSubarrays(int[] arr, int k, int threshold) { threshold * k; int res 0, curSum 0; for (int R 0; R arr.length; R) { curSum arr[R]; if (R k - 1) { if (curSum threshold) { res; } curSum - arr[R - k 1]; } } return res; } }class Solution { public: int numOfSubarrays(vectorint arr, int k, int threshold) { threshold * k; int res 0, curSum 0; for (int R 0; R arr.size(); R) { curSum arr[R]; if (R k - 1) { if (curSum threshold) { res; } curSum - arr[R - k 1]; } } return res; } };class Solution { /** * param {number[]} arr * param {number} k * param {number} threshold * return {number} */ numOfSubarrays(arr, k, threshold) { threshold * k; let res 0, curSum 0; for (let R 0; R arr.length; R) { curSum arr[R]; if (R k - 1) { if (curSum threshold) { res; } curSum - arr[R - k 1]; } } return res; } }public class Solution { public int NumOfSubarrays(int[] arr, int k, int threshold) { threshold * k; int res 0, curSum 0; for (int r 0; r arr.Length; r) { curSum arr[r]; if (r k - 1) { if (curSum threshold) { res; } curSum - arr[r - k 1]; } } return res; } }func numOfSubarrays(arr []int, k int, threshold int) int { threshold * k res, curSum : 0, 0 for r : 0; r len(arr); r { curSum arr[r] if r k-1 { if curSum threshold { res } curSum - arr[r-k1] } } return res }class Solution { fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int { val target threshold * k var res 0 var curSum 0 for (r in arr.indices) { curSum arr[r] if (r k - 1) { if (curSum target) { res } curSum - arr[r - k 1] } } return res } }class Solution { func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) - Int { let target threshold * k var res 0 var curSum 0 for r in 0..arr.count { curSum arr[r] if r k - 1 { if curSum target { res 1 } curSum - arr[r - k 1] } } return res } }impl Solution { pub fn num_of_subarrays(arr: Veci32, k: i32, threshold: i32) - i32 { let k k as usize; let target threshold * k as i32; let mut res 0; let mut cur_sum 0; for r in 0..arr.len() { cur_sum arr[r]; if r k - 1 { if cur_sum target { res 1; } cur_sum - arr[r - k 1]; } } res } }复杂度分析时间复杂度O(n)——单次线性扫描。空间复杂度O(1)额外空间。其中 n 为数组arr的长度k 为子数组长度。对比前三种写法这一版把「加右 → 判定 → 减左」统一收敛在一个循环里同时完成了阈值换算代码最简洁、语义最干净是实际面试与工程中的推荐写法。四种解法对比一览解法核心思路时间复杂度空间复杂度适用场景暴力枚举每个窗口独立重算和O(n·k)O(1)仅用于理解题意、小数据前缀和预计算累计和区间和 O(1) 查询O(n)O(n)需要大量任意区间查询的场景滑动窗口 I维护运行中和加右减左O(n)O(1)定长窗口的通用解法滑动窗口 II阈值 × k 后直接比和O(n)O(1)定长窗口 平均值判定的最优解常见陷阱Common Pitfalls整数除法截断Integer Division Truncation在 Java、C、Go 等语言中sum / k是整数除法结果会向零截断。例如sum 15、k 4时15 / 4得到的是3而不是3.75。当真实平均值已经达到阈值、但截断后的整数结果低于阈值时就会产生假阴性漏计。规避方法正是解法四先把threshold乘以k得到目标窗口和再直接比较curSum threshold * k全程不出现除法。这一点在 Python 之外的语言中尤其重要——Python 3 的/是精确浮点除法而 Go、Java、C 的/对两个整数操作数执行整除。仓库中 kotlin/1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold.kt 等实现同样采用sum / k threshold的写法若要严格规避截断可在实际提交时改用「阈值 × k」版本。重复计算窗口和Recalculating the Window Sum最常见的低效写法是每个窗口都从头累加导致 O(n·k) 的时间复杂度。滑动窗口通过维护运行中的curSum每个窗口只做一次「加新元素、减旧元素」的 O(1) 更新即可。窗口边界的越界错误Off-By-One Errors in Window Boundaries滑动时最容易出错的是下标计算。需要始终保证窗口内恰好包含 k 个元素。常见错误包括右指针起点设错例如从k而不是k - 1开始判定收缩窗口的时机算错例如在窗口尚未满 k 个元素时就提前移除左端元素移除元素时下标写错应移除的是arr[R - k 1]即当前窗口中最旧的那个元素。可以用R - L 1 k或R k - 1作为「窗口已满」的判据配合少量边界用例如n k、k 1自测能有效规避此类错误。总结本题是「定长滑动窗口 平均值判定」的经典模板题暴力枚举 O(n·k) 帮助理解问题前缀和 O(n)/O(n) 展示了区间和查询的空间换时间思路滑动窗口 O(n)/O(1) 是定长窗口的最优形态而「阈值 × k」的改写不仅让代码更简洁还顺带解决了 Java、C、Go 等语言的整数除法截断问题。仓库中 9 种语言的实现均可直接对照运行cpp、go、java、javascript、kotlin、python、swift、csharp适合作为掌握滑动窗口思想的入门练手与多语言对照样本。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
