本文涉及的基础知识点

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

LeetCode2444. 统计定界子数组的数目

给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
子数组中的 最小值 等于 minK 。
子数组中的 最大值 等于 maxK 。
返回定界子数组的数目。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。
示例 2：
输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。
参数范围：
2 <= nums.length <= 10⁵
1 <= nums[i], minK, maxK <= 10⁶

四指针

$\forall$i，nums[i…j]存在minK的最小解为j1。nums[i…j]存在maxK的最小解为j2。nums[i…j]存在比minK小或比maxK大的数的最小解为j3。
如果存在界定子数组[i…j]，则j >= max(j1,j2)且j < j3。即：ans += max(0,j3-max(j1,j2))
如果j1 < i，则j1++。while( nums[j1] != mink); j1++;
j2,j3类似。
时间复杂度：O(n)

代码

核心代码

class Solution {
		public:
			long long countSubarrays(vector<int>& nums, int minK, int maxK) {
				const int N = nums.size();
				long long ans = 0;
				for (int i = 0, j1 = -1, j2 = -1, j3 = -1; i < N; i++) {
					if (j1 < i) {
						j1++;
						while ((j1 < N) && (nums[j1] != minK)) { j1++; }
					}
					if (j2 < i) {
						j2++;
						while ((j2 < N) && (nums[j2] != maxK)) { j2++; }
					}
					if (j3 < i) {
						j3++;
						while ((j3 < N) && (nums[j3] >= minK)&&(nums[j3] <= maxK)) { j3++; }
					}
					ans += max(0,j3 - max(j1, j2));
				}
				return ans;
			}
		};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}
int main()
{
	vector<int> nums;
	int minK,  maxK;
	{
		Solution sln;
		nums = { 1, 3, 5, 2, 7, 5 }, minK = 1, maxK = 5;
		auto res = sln.countSubarrays(nums, minK, maxK);
		Assert(2LL, res);
	}
	{
		Solution sln;
		nums = { 1, 1, 1, 1 }, minK = 1, maxK = 1;
		auto res = sln.countSubarrays(nums, minK, maxK);
		Assert(10LL, res);
	}
}