难度: Medium
给你一个整数数组 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 <= 1051 <= nums[i] <= 1061 <= k <= 105运行时间: 100 ms
内存: 27.0 MB
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
t=max(nums)
ans,left,cnt=0,0,0
for i in nums:
if i==t:
cnt+=1
while cnt==k:
if nums[left]==t:
cnt-=1
left+=1
ans+=left
return ans
本题解使用了双指针方法来统计满足条件的子数组数量。首先，找到数组中的最大元素t。然后，使用两个指针left和right来遍历数组，right指针向右移动来扩展当前考虑的子数组，left指针向右移动来缩小子数组。当子数组中最大元素t的出现次数达到k时，left指针开始移动，直到t的出现次数再次小于k。这样，对于每个right指针的位置，都可以计算出以right为结束点的、满足条件的子数组数量，即left指针当前的位置数。最后，将所有这些数量累加起来即为答案。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
t=max(nums) # 找到数组中的最大元素
ans,left,cnt=0,0,0 # 初始化答案，左指针，和最大元素的计数
for i in nums: # 遍历数组
if i==t: # 如果当前元素是最大元素
cnt+=1 # 增加计数
while cnt==k: # 当最大元素出现次数达到k时
if nums[left]==t: # 如果左指针指向的元素是最大元素
cnt-=1 # 减少计数
left+=1 # 移动左指针
ans+=left # 累加以当前右指针为结束点的满足条件的子数组数量
return ans # 返回答案
双指针策略通过维护一个动态的窗口来确保不漏掉任何符合条件的子数组。右指针`right`负责扩展窗口以包括更多元素，而左指针`left`则在条件满足（最大元素出现次数达到k）后开始移动以缩小窗口直到条件不再满足。每次右指针移动后，窗口内的所有以`right`为结束点的子数组都会被考虑，因为通过移动左指针，我们可以找到所有可能的以`right`为结束点的子数组的起始点。这样可以确保每个符合条件的子数组都被精确地统计一次。
题解中的策略不会导致子数组的重复计数。当最大元素的计数达到k时，左指针移动是为了找到新的子数组的起始点，每移动一次左指针，代表原先计数的子数组已经不再被考虑，因此每个子数组只会被计算一次。左指针的每一次移动都对应着一个新的子数组起始点的确定，从而确保计数的唯一性。
题解中累加左指针的位置数的方法基于每次右指针扩展后，左指针位置到右指针位置形成的区间内的所有子数组都是满足条件的子数组。因此，对于每个右指针位置，只需要累加左指针的位置数即可得到以该右指针位置为结束点的所有满足条件的子数组数量。这是因为每个以`right`为结束点的子数组都可以通过左指针的不同位置唯一确定。
当最大值t的出现次数超过k时，左指针继续移动直到最大元素的出现次数减少到小于k。这个过程确保了每个计数的子数组都恰好或至少包含k次最大元素，但不会引入额外的计数。只有当最大元素的计数达到或超过k，子数组才符合条件，左指针的移动是为了确保所有统计的子数组始终满足最大元素至少出现k次的条件。