2302. Count Subarrays With Score Less Than K
https://leetcode.com/problems/count-subarrays-with-score-less-than-k/
计算符合
阵列元素 * 阵列大小 < K
的子阵列总数
思路：
因为是说子阵列 子阵列=母阵列切片
代表几乎一定是 Sliding Windows
从 left = 0, right = 0 开始
每轮开始先加上 nums[right]
之后 while 跑 sum * len >= k
慢慢把 nums[left] 蛋雕直到不符合反向条件跳出
之后 count += (right - left + 1)
这边加的这一串代表以 nums[right] 为一定有的成员
蛋雕后新的 nums[left] 到 nums[right] 每个子阵列
举例说 left = 0, right = 3
就是 [0~3], [1~3], [2~3], [3~3] 共四个子阵列
所以每次结束都要加 因为每次的 right 都不一样
最后算完的 count 就是全部的可能性
Code:
impl Solution {
pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
let mut count: i64 = 0;
let mut sum: i64 = 0;
let mut left = 0;
for right in 0..nums.len() {
sum += nums[right] as i64;
while sum * (right - left + 1) as i64 >= k {
sum -= nums[left] as i64;
left += 1;
}
count += (right - left + 1) as i64;
}
count
}
}