一个长度为 n 下标从 0 开始的整数数组 arr 的 不平衡数字 定义为，在 sarr = sorted(arr) 数组中，满足以下条件的下标数目：

  • 0 <= i < n - 1 ，和
  • sarr[i+1] - sarr[i] > 1

这里，sorted(arr) 表示将数组 arr 排序后得到的数组。

给你一个下标从 0 开始的整数数组 nums ，请你返回它所有 子数组 的 不平衡数字 之和。

子数组指的是一个数组中连续一段 非空 的元素序列。

 

示例 1：

输入：nums = [2,3,1,4]
输出：3
解释：总共有 3 个子数组有非 0 不平衡数字：
- 子数组 [3, 1] ，不平衡数字为 1 。
- 子数组 [3, 1, 4] ，不平衡数字为 1 。
- 子数组 [1, 4] ，不平衡数字为 1 。
其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 3 。

示例 2：

输入：nums = [1,3,3,3,5]
输出：8
解释：总共有 7 个子数组有非 0 不平衡数字：
- 子数组 [1, 3] ，不平衡数字为 1 。
- 子数组 [1, 3, 3] ，不平衡数字为 1 。
- 子数组 [1, 3, 3, 3] ，不平衡数字为 1 。
- 子数组 [1, 3, 3, 3, 5] ，不平衡数字为 2 。
- 子数组 [3, 3, 3, 5] ，不平衡数字为 1 。
- 子数组 [3, 3, 5] ，不平衡数字为 1 。
- 子数组 [3, 5] ，不平衡数字为 1 。
其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 8 。

 

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= nums.length

比赛ac代码

复杂度

时间复杂度 O()
空间复杂度 O()
可以优化为 O()

思路分析

数据量为1000，暴力O()大约O()，可以考虑将第三次的循环改为bisect_left，降低复杂度O()
维护递增区间[L,R]，该区间不平衡数字之和为cnt，则[L,R+1]区间需要判断nums[R+1]在递增数组的位置，
idx = bisect.bisect_left(last,nums[R+1])
1、如果小于递增区间最小值且差值大于1，则cnt+=1
2、如果大于递增区间最大值且差值大于1，则cnt+=1
3、如果在区间内，则判断nums[R+1]和last[idx-1]和last[idx+1]差值大小
cnt += ((nums[R+1] - last[idx-1]) > 1) + ((last[idx+1] - nums[R+1]) > 1) - ((last[idx+1] - last[idx-1]) > 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0]*n for _ in range(n)]
        for l in range(n):
            last = []
            for r in range(l+1,n):
                if not last:
                    last = [min(nums[l],nums[r]),max(nums[l],nums[r])]
                    if abs(last[1]-last[0]) > 1:
                        dp[l][r]+=1
                else:
                    idx = bisect_left(last,nums[r])
                    dp[l][r] = dp[l][r-1]
                    if idx == 0:
                        if last[0] - nums[r] > 1:
                            dp[l][r] += 1
                    elif idx == len(last):
                        if nums[r] - last[-1] > 1:
                            dp[l][r] += 1
                    else:
                        if nums[r] - last[idx-1] > 1:
                            dp[l][r] += 1
                        if last[idx] - nums[r] > 1:
                            dp[l][r] += 1
                        if last[idx] - last[idx-1] > 1:
                            dp[l][r] -= 1
                    last.insert(idx,nums[r])
        print(dp)
        return sum(sum(item) for item in dp)

灵神代码

思路1

复杂度
时间复杂度 O()
空间复杂度 O()
将递增数组通过hash进行表示，对于y = nums[r]，考虑vis[y-1],vis[y],vis[y+1]是否出现过vis数组中
1、如果vis[y]访问过，则不影响冲突数量，cnt = cnt
1、如果vis[y-1]访问过，cnt = 1 - vis[y-1] # 默认vis[y]没访问过+1
2、如果vis[y+1]访问过，cnt = 1 - vis[y+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for l,x in enumerate(nums):
            vis = [False]*(n+2)
            vis[x] = True
            cnt = 0
            for r in range(l+1,n):
                y = nums[r]
                if not vis[y]:
                    cnt += 1 - vis[y-1] - vis[y+1]
                    vis[y] = True
                ans+=cnt
        return ans

优化

重复对vis数组进行赋值，可以进行优化vis数组，vis数组记录区间开始的left下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        vis = [n]*(n+2)  # 初始赋值需要进行修改
        for l,x in enumerate(nums):
            vis[x] = l   # 此处记录left下标
            cnt = 0
            for r in range(l+1,n):
                y = nums[r]
                if vis[y]!=l: # 以left开始当前y值并未访问过
                    cnt += 1 - (vis[y-1] == l) - (vis[y+1]==l)
                    vis[y] = l # 更新y值以left开始访问过
                ans+=cnt

思路2

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