本文涉及的基础知识点

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

LeetCode2762. 不间断子数组

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：
i，i + 1 ，…，j 表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。
请你返回 不间断 子数组的总数目。
子数组是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。
示例 2：
输入：nums = [1,2,3]
输出：6
解释：
大小为 1 的不间断子数组：[1], [2], [3] 。
大小为 2 的不间断子数组：[1,2], [2,3] 。
大小为 3 的不间断子数组：[1,2,3] 。
不间断子数组的总数目为 3 + 2 + 1 = 6 。
提示：
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

C++滑动窗口

n = nums.size
性质一：如果nums[i…j]不是合法子数组，则j1 >=j，nums[i…j1]也不是。我们只需寻找最大j。
性质二：如果nums[i…j]是合法数组，则j2<j， nums[i…j2]是合法子数组。故以i开始的合法子数组的数量是：j-i+1。
性质三：如果nums[i1…j]是合法子数组，则nums[i1+1…j]必定合法。故i++后，j无需复位。
滑动窗口：左闭右开区间。枚举i，j是以下情况之一：
一,j等于N。
二，nums[i…j]存在绝对值相差2的数对。
多键有序集合setValue。
滑动左端点：
mValue[nums[i]]–;
如果值为0，则要删除。这样映射顶多三个，增加和删除可以看成O(n)。
滑动右端点：
auto Is = & {return (nums[j] - mValue.begin()->first <= 2) && (mValue.rbegin()->first - nums[j] <= 2); };
if(mValue.empty() || Is() {mValue[nums[j]]++; j++;}

ans += j-i ;

代码

核心代码

class Solution {
		public:
			long long continuousSubarrays(vector<int>& nums) {
				const int N = nums.size();
				map<int, int> mValue ;
				long long ans = 0;
				for (int i = 0, j = 0; i < N; i++) {
					auto Is = [&]() {return (nums[j] - mValue.begin()->first <= 2) && (mValue.rbegin()->first - nums[j] <= 2); };
					while (j < N ) {
						if (mValue.empty() || Is())
						{
							mValue[nums[j]]++; j++;
						}
						else {break;}
					}
					ans += j - i;
					mValue[nums[i]]--;
					if (0 == mValue[nums[i]]) {
						mValue.erase(nums[i]);
					}
				}
				return ans;
			}
		};

单元测试

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