2962. 統計最大元素出現至少 K 次的子數組
給你一個整數數組 nums 和一個 正整數 k 。
請你統計有多少滿足 「 nums 中的 最大 元素」至少出現 k 次的子數組，并返回滿足這一條件的子數組的數目。
子數組是數組中的一個連續元素序列。
示例 1：
輸入：nums = [1,3,2,3,3], k = 2
輸出：6
解釋：包含元素 3 至少 2 次的子數組為：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
示例 2：
輸入：nums = [1,4,2,1], k = 3
輸出：0
解釋：沒有子數組包含元素 4 至少 3 次。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= k <= 105
題解
如標題所示，本題采用滑動數組進行解題
題目要求所有滿足條件的子數組
那么我們自然需要考慮所有的子數組
我們該如何做到呢
首先看看如何枚舉所有的子數組
我們可以用一個循環枚舉出所有子數組可能的開頭，然后內層再寫一個循環枚舉所有可能的結尾，這樣就枚舉了所有的子數組
那么滑動數組又該如何考慮到所有的子數組呢？
類似的，我們可以寫一個循環枚舉出所有子數組的結尾 i
然后使用指針 l=0 作為子數組的開頭，那么 l 與 i 就是滑動窗口的區間
我們使用變量 count 記錄滑動窗口中的最大值的個數，res=0 記錄返回值
此時 i 作為窗口的右邊不斷右移
當 count == k 時，此時的滑動窗口滿足條件，我們找到了一個答案
但是問題是，接下來我們要如移動滑動窗口呢？
將 i 向右移，還是將 l 向右移
注意到，我們第一層循環是枚舉所有子數組的結尾
只要對于每一種結尾，我們都找到所有可能的子數組就能解決問題
但是我們顯然不能枚舉開頭 l ，否則與枚舉就一樣了，時間復雜高
當 count == k 時，我們可以將 窗口左邊 l 右移，直到 count != k
那么對于此時的 i ，此時所有以 l 的左邊為開頭的子數組 [ l, i ] 都是滿足條件的
也就是我們找到了以 i 結尾的所有滿足條件的子數組
所以滑動窗口 [ l, i ] 的含義就是以 i 結尾的，第一個不滿足條件的子數組
res+=l ，枚舉下一個 i
如果 count != k，那么 l 的位置不變，res+=l
如果count==k，那么接著移動 l 直到滑動窗口不滿足條件
總計滑動窗口劃過一次數組，時間復雜度為 O(n)
代碼如下↓
long long countSubarrays(int* nums, int numsSize, int k) {int l=0;int max=0;long res=0;int count=0;for(int i=0;i<numsSize;i++){if(nums[i]>max){max=nums[i];}}for(int i=0;i<numsSize;i++){if(nums[i]==max){count++;}while(count==k)//怎么說呢，每次i就是子數組的右端點，每次當count的個數為k的時候，就將l右移，直到count<k，那么l之前的所有字符都可以作為子數組的左端點，也就是說以i為右端點的滿足條件的子數組有left個。然后i繼續右移，直到count再次==k，然后重復以上過程，left左邊的所有字符同樣滿足條件，count的個數肯定>=k，所以res+=left{if(nums[l]==max){count--;}l++;}res+=l;printf("%d\n",l);}return res;
}
