2762. 不间断子数组

🟠 🔖 队列 数组 有序集合 滑动窗口 单调队列 堆（优先队列） 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number ofcontinuous subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [5,4,2,4]
Output: 8
Explanation:
Continuous subarray of size 1: [5], [4], [2], [4].
Continuous subarray of size 2: [5,4], [4,2], [2,4].
Continuous subarray of size 3: [4,2,4].
Thereare no subarrys of size 4.
Total continuous subarrays = 4 + 3 + 1 = 8.
It can be shown that there are no more continuous subarrays.

Example 2:

Input: nums = [1,2,3]
Output: 6
Explanation:
Continuous subarray of size 1: [1], [2], [3].
Continuous subarray of size 2: [1,2], [2,3].
Continuous subarray of size 3: [1,2,3].
Total continuous subarrays = 3 + 2 + 1 = 6.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

题目大意

给你一个下标从 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^5
1 <= nums[i] <= 10^9

解题思路

滑动窗口：
- 本题要求计算连续子数组，且子数组需要满足一定的条件，滑动窗口是一个非常适合解决此类问题的技巧。
- 滑动窗口的核心在于，通过移动窗口的边界（起点 i 和终点 j）动态调整窗口范围，从而高效地确定满足条件的子数组。
使用哈希表记录窗口状态：
- 为了高效地判断窗口内元素是否满足条件，可以使用一个哈希表 map 记录窗口内每个数的频率。
窗口合法性检查：
- 判断窗口是否满足条件的方法：窗口内的元素必须满足任意两个数 nums[i] 和 nums[j] 的绝对差值不超过 2。
- 对于滑动窗口的每个位置 j，通过一个辅助函数 getCount(num)，统计 num 及其相邻值 num±1 和 num±2 的出现频次，与当前窗口长度 (j - i + 1) 对比，从而判断当前窗口是否满足条件。
  - 如果 getCount(num) == (j - i + 1)，说明窗口中所有数的绝对差值都不超过 2，所有以 j 为右边界的子数组的个数为 (j - i + 1)，将其加入子数组总数中。
  - 如果 getCount(num) < (j - i + 1)，说明窗口中出现了绝对差值超过 2 的数字，逐步收缩左边界 i，同时更新哈希表 map。
遍历数组 nums：
- 将当前元素加入窗口（更新 map）。
- 检查当前窗口是否满足条件。如果不满足，则收缩窗口（调整 i 并更新 map）。
- 累加以 j 为右边界的子数组数：total += (j - i + 1)。
返回结果：
- 返回 total 作为结果。

复杂度分析

时间复杂度：O(n)，遍历数组的时间复杂度为 O(n)，哈希表的插入、删除、查询操作时间复杂度为 O(1)。
空间复杂度：O(n)，使用了一个哈希表 map，其大小取决于窗口中不同数字的数量，最坏情况下，空间复杂度为 O(n)。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var continuousSubarrays = function (nums) {
	const n = nums.length;
	let i = 0; // 滑动窗口左边界
	let total = 0; // 满足条件的子数组总数
	let map = new Map(); // 哈希表记录窗口内数字出现的频率

	// 辅助函数：统计num及其相邻数字的总频率
	const getCount = (num) => {
		return (
			(map.get(num) || 0) +
			(map.get(num - 1) || 0) +
			(map.get(num - 2) || 0) +
			(map.get(num + 1) || 0) +
			(map.get(num + 2) || 0)
		);
	};

	// 遍历数组
	for (let j = 0; j < n; j++) {
		// 将当前元素加入窗口
		map.set(nums[j], (map.get(nums[j]) || 0) + 1);

		// 调整窗口的左边界，确保窗口合法
		while (j - i + 1 > getCount(nums[j])) {
			map.set(nums[i], map.get(nums[i]) - 1); // 移除左边界元素
			i++; // 收缩左边界
		}

		// 累加以j为右边界的子数组数
		total += j - i + 1;
	}

	return total;
};

2762. 不间断子数组

# 2762. 不间断子数组

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

2762. 不间断子数组

题目

题目大意

解题思路

复杂度分析

代码