本文涉及的基础知识点

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

LeetCode2537. 统计好子数组的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。
示例 2：
输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：

• [3,1,4,3,2,2] 有 2 对。
• [3,1,4,3,2,2,4] 有 3 对。
• [1,4,3,2,2,4] 有 2 对。
• [4,3,2,2,4] 有 2 对。
  提示：
  1 <= nums.length <= 10⁵
  1 <= nums[i], k <= 10⁹

滑动窗口

性质一：j1<j2，nums[i1…j1]是好子数组，$\to$ nums[i1…j2]也一定是好数组。每个i，只需要求最小的j。
性质二：i1<i2，nums[i1…j1]不是好数组，则nums[i2…j1]也不是好数组。因为值相同的下标对，前者不少于后者。故j无需要复位。故时间复杂度：O(n)。
哈希映射mCnt 记录滑动窗口各元素的数量。cnt记录相同的点对数量。
滑动窗口左端点右移：
mCnt[nums[i]]–
cnt -= mCnt[nums[i]]
nums[i…j]包括i的点对数量，等于nums[i+1…j]中和nums[i]相等的数量。
同理滑动窗口右端点右移：
cnt += mCnt[nums[j]]
mCnt[nums[j]]++

代码

核心代码

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

单元测试

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