---
# System prepended metadata

title: 2537. Count the Number of Good Subarrays
tags: [Leetcode]

---

<style>
    html, body, .ui-content {
    background: #222222;
    color: #00BFFF;
}
    /* 設定 code 模板 */
    .markdown-body code,
.markdown-body tt {
    background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
    color: #ddd;
    background-color: #00000036;
}
.hljs-tag {
    color: #ddd;
}
.token.operator {
  background-color: transparent;
}
   
</style>

###### tags: `Leetcode`

# 2537. Count the Number of Good Subarrays

###### Link : https://leetcode.com/contest/weekly-contest-328/problems/count-the-number-of-good-subarrays/

## 題目
找到pair超過k的所有子陣列數量
## 程式碼

```cpp=
class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long ans = 0, _count = 0;//_count目前子陣列擁有的pair數
        int locate = 0;//子陣列的起點
        map<int, int> flag;//數字出現多少次
        for(int i = 0; i < nums.size(); i++){
            _count += flag[nums[i]];//加上數字出現幾次 沒出現過+0
            flag[nums[i]]++;//出現次數+1
            while(_count >= k){
                ans += nums.size() - i;//加上符合條件的子陣列會有多少個
                flag[nums[locate]]--;//扣掉目前子陣列最前面的數字出現次數-1
                _count -= (flag[nums[locate]] - 1);//扣掉最前面數字後，需扣掉的pair數量
                locate++;//子陣列的起點+1
            }
        }
        while(_count >= k && locate < nums.size()){//避免存在符合條件的子陣列都在最右邊
            ans += 1;
            _count -= (flag[nums[locate]] - 1);
            flag[nums[locate]]--;
            locate++;
        }
        return ans;
    }
};
```