跳至主要內容

2762. 不间断子数组

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

解题思路

  1. 滑动窗口：

    • 本题要求计算连续子数组，且子数组需要满足一定的条件，滑动窗口是一个非常适合解决此类问题的技巧。
    • 滑动窗口的核心在于，通过移动窗口的边界（起点 i 和终点 j）动态调整窗口范围，从而高效地确定满足条件的子数组。

  2. 使用哈希表记录窗口状态：

    • 为了高效地判断窗口内元素是否满足条件，可以使用一个哈希表 map 记录窗口内每个数的频率。

  3. 窗口合法性检查：

    • 判断窗口是否满足条件的方法：窗口内的元素必须满足任意两个数 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。

  4. 遍历数组 nums：

    • 将当前元素加入窗口（更新 map）。
    • 检查当前窗口是否满足条件。如果不满足，则收缩窗口（调整 i 并更新 map）。
    • 累加以 j 为右边界的子数组数：total += (j - i + 1)。

  5. 返回结果：

    • 返回 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;
};
Copyright © 2025 2xiao