What is the best pattern to solve Count Subarrays With Score Less Than K?

Binary search over the valid answer space combined with sliding window is the recommended pattern for this problem.

Can I use brute force to count subarrays?

Brute force works only for small arrays; for larger arrays it will exceed time limits due to O(n^2) complexity.

Do I need to consider single-element subarrays?

Yes, each single element forms a valid subarray and must be counted if its score is less than k.

How does the sliding window help in this problem?

Sliding window efficiently maintains running sums to check score constraints without recomputing subarray sums repeatedly.

What is a common mistake with binary search here?

A common mistake is off-by-one errors when determining maximum subarray length that keeps the score strictly less than k.

#2302

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

统计得分小于 K 的子数组数目

一个数组的分数定义为数组之和乘以数组的长度。比方说， [1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数严格小于 k 的非空整数子数组数目。子数组是数组…

数组二分查找滑动窗口前缀和

题目描述

一个数组的分数定义为数组之和乘以数组的长度。

比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。

子数组 是数组中的一个连续元素序列。

示例 1：

输入：nums = [2,1,4,3,5], k = 10
输出：6
解释：
有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。 
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。

示例 2：

输入：nums = [1,1,1], k = 5
输出：5
解释：
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10¹⁵

lightbulb

解题思路

方法一：前缀和 + 二分查找

我们先计算出数组 $\textit{nums}$ 的前缀和数组 $s$ ，其中 $s[i]$ 表示数组 $\textit{nums}$ 前 $i$ 个元素的和。

接下来，我们枚举数组 $\textit{nums}$ 每个元素作为子数组的最后一个元素，对于每个元素，我们可以通过二分查找的方式找到最大的长度 $l$ ，使得 $s[i] - s[i - l] \times l < k$ 。那么以该元素为最后一个元素的子数组个数即为 $l$ ，我们将所有的 $l$ 相加即为答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        s = list(accumulate(nums, initial=0))
        ans = 0
        for i in range(1, len(s)):
            l, r = 0, i
            while l < r:
                mid = (l + r + 1) >> 1
                if (s[i] - s[i - mid]) * mid < k:
                    l = mid
                else:
                    r = mid - 1
            ans += l
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is processed at most twice in the sliding window. Space complexity is O(1) additional space beyond the input array if prefix sums are maintained in place.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for binary search usage on the maximum valid length to see if the candidate recognizes the answer-space pattern.
question_mark
Observe if the candidate optimizes with sliding window rather than brute-force O(n^2) subarray enumeration.
question_mark
Check for careful handling of single-element subarrays and edge score thresholds to avoid off-by-one mistakes.

warning

常见陷阱

外企场景

error
Brute-force enumeration of all subarrays leads to TLE for large arrays; always consider binary search or prefix sum optimization.
error
Failing to account for single-element subarrays can cause undercounting.
error
Incorrectly updating sum or length in sliding window may miscount subarrays crossing the threshold exactly at k.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count subarrays with sum less than k ignoring the length multiplier.
arrow_right_alt
Find maximum length subarray with score less than k instead of counting all.
arrow_right_alt
Return subarrays themselves rather than counts, applying the same binary search check.

help

常见问题

外企场景

继续练习

#2271 毯子覆盖的最多白色砖块数 #2398 预算内的最多机器人数目 #2106 摘水果