2537.统计好子数组的数目

链接：2537.统计好子数组的数目
难度：Medium
标签：数组、哈希表、滑动窗口
简介：给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

题解 1 - cpp

• 编辑时间：2023-01-15
• 执行用时：168ms
• 内存消耗：73.3MB
• 编程语言：cpp
• 解法介绍：枚举最右侧节点，对每个最右侧节点统计最近的左侧节点，此时以该节点结尾大于K的有left+1个。

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long ans = 0, n = nums.size(), cnt = 0, l = 0;
        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) {
            cnt += m[nums[i]]++;
            while (l < i && cnt - (m[nums[l]] - 1) >= k) cnt -= m[nums[l++]]-- - 1;
            if (cnt >= k) ans += l + 1;
        }
        return ans;
    }
};

题解 2 - rust

• 编辑时间：2023-01-15
• 执行用时：44ms
• 内存消耗：4.9MB
• 编程语言：rust
• 解法介绍：同上。

use std::collections::HashMap;
impl Solution {
    pub fn count_good(nums: Vec<i32>, k: i32) -> i64 {
        let mut ans: i64 = 0;
        let mut cnt = 0;
        let mut l = 0;
        let n = nums.len();
        let mut m = HashMap::<i32, i32>::new();
        let mut i = 0;
        while i < n {
            let num = nums[i];
            cnt += m.get(&num).unwrap_or(&0);
            if !m.contains_key(&num) {
                m.insert(num, 1);
            } else {
                *m.get_mut(&num).unwrap() += 1;
            }
            while l < i && cnt - (m.get(&nums[l]).unwrap() - 1) >= k {
                let v = m.get_mut(&nums[l]).unwrap();
                *v -= 1;
                cnt -= *v;
                l += 1;
            }
            if cnt >= k {
                ans += (l + 1) as i64;
            }
            i += 1;
        }
        ans
    }
}