本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

LeetCode2962. 统计最大元素出现至少 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 <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= 10⁵

滑动窗口

性质一：j1<j2,如果nums[i…j1]符合要求，则nums[i…j2]一定符合要求。针对每个i，只需要求出最小j。
性质二：i1<i2，如果nums[i1…j1]不符合要求，则num[i2…j1]也一定不符合要求。因为后者最大元素出现的次数小于前者。故i++后，j不需要从0开始。故时间复杂度：O(n)。
nums[i…j-1]如果不符合要求，需要排除。

代码

核心代码

class Solution {
		public:
			long long countSubarrays(vector<int>& nums, int k) {
				const int N = nums.size();
				const int iMax = *max_element(nums.begin(), nums.end());
				long long ans = 0;
				int cnt = 0;
				for (int i = 0, j = 0; i < N; i++) {
					while ((j < N) && (cnt < k)) {
						cnt += (iMax == nums[j]); j++;
					}
					if (cnt >= k) {
						ans += N - j + 1;
					}
					cnt -= (iMax == nums[i]);
				}
				return ans;
			}
		};

单元测试

vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, 3, 2, 3, 3 }, k = 2;
			auto res = Solution().countSubarrays(nums, k);
			AssertEx(6LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,4,2,1 }, k = 3;
			auto res = Solution().countSubarrays(nums, k);
			AssertEx(0LL, res);
		}