给你一个下标从 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 <= 105
  • 1 <= nums[i] <= 109

比赛没有ac

灵神代码

思路 滑动窗口

复杂度
时间复杂度 O()
空间复杂度 O()

难点：维护区间的最值，容易考虑线段树、树状数组进行求解，所以放弃了
区间最值通过hash进行维护
left指针固定，right指针往右扩展，right每扩展一次检查当前hash区间最值是否满足要求，如果不满足则left++，进行弹出，直到满足为止
注：本题差值为固定的2，如果是参数k，则复杂度为O()

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        #滑动窗口
        left = 0
        ans = 0
        d = Counter() # hash进行维护区间最值
        for right,x in enumerate(nums):
            d[x] += 1
            while max(d) - min(d) > 2:
                y = nums[left]
                d[y] -= 1     # 考虑数值重复
                if d[y] == 0:
                    del d[y]
                left += 1
            ans += right - left + 1 # 当前滑动窗口以right为结尾的子数组个数，left为最远的位置
        return ans