Count Subarrays With Sum Less Than K
Given an array of positive integers `nums` and a positive integer `k`, return the number of contiguous subarrays whose sum is strictly less than $k$.
**Constraints:**
-
\le n \le 10^5$ where $n$ is the length of `nums`
-
\le \text{nums}[i] \le 10^4$
-
\le k \le 10^9$
**Example 1:**
- Input: `nums = [2, 1, 4, 3]`, `k = 5`
- Output: `5`
- Explanation: The valid subarrays are `[2]` (sum 2), `[1]` (sum 1), `[4]` (sum 4), `[3]` (sum 3), and `[2,1]` (sum 3). Subarrays like `[1,4]` (sum 5) and `[4,3]` (sum 7) are excluded because their sums are not strictly less than 5.
**Example 2:**
- Input: `nums = [1, 1, 1]`, `k = 3`
- Output: `5`
- Explanation: `[1]` appears 3 times (sums to 1 each), `[1,1]` appears 2 times (sums to 2 each). All five have sum < 3. The full array `[1,1,1]` sums to 3, which is not strictly less, so it is excluded.
Open the full interactive solver, hints, and worked solution →