Re: [閒聊] 每日leetcode

[yam276 (史萊哲林的優等生)]

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
    }
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1745834223.A.1D8.html