What is the main idea for Sum of Imbalance Numbers of All Subarrays?

Fix a left index, extend the right index, and maintain the current imbalance with neighbor checks around the new value. The whole trick is that only x-1 and x+1 can change the sorted-gap count when x is added.

Why does checking only x-1 and x+1 work?

Imbalance counts adjacent gaps in sorted order. When x is inserted, only the numbers immediately next to x in value can create a new separated block or merge two existing blocks, so distant values never change that local effect.

Why do duplicates not increase the imbalance?

A duplicate does not introduce a new value position in sorted order, so it cannot create a new adjacent difference greater than 1. In this problem, duplicates should leave the running imbalance unchanged.

Is an ordered set required for this problem?

Not for the given constraints. Since nums[i] is between 1 and nums.length, a hash set or boolean seen array is enough to support the neighbor checks that drive the O(n^2) solution.

What is the usual wrong approach for this exact pattern?

The common miss is to sort every subarray and count gaps from scratch. That ignores the incremental structure of the problem and turns a local-update task into a much slower repeated-sorting solution.

#2763

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

所有子数组中不平衡数字之和

一个长度为 n 下标从 0 开始的整数数组 arr 的不平衡数字定义为，在 sarr = sorted(arr) 数组中，满足以下条件的下标数目： 0 ，和 sarr[i+1] - sarr[i] > 1 这里， sorted(arr) 表示将数组 arr 排序后得到的数组。给你一个下标从 0…

数组哈希表有序集合

题目描述

一个长度为 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

lightbulb

解题思路

方法一：枚举 + 有序集合

我们可以先枚举子数组的左端点 $i$ ，对于每个 $i$ ，我们从小到大枚举子数组的右端点 $j$ ，并且用一个有序列表维护当前子数组中的所有元素，用一个变量 $cnt$ 维护当前子数组的不平衡数字。

对于每个数字 $nums[j]$ ，我们在有序列表中找到第一个大于等于 $nums[j]$ 的元素 $nums[k]$ ，以及最后一个小于 $nums[j]$ 的元素 $nums[h]$ ：

如果 $nums[k]$ 存在，并且 $nums[k]$ 与 $nums[j]$ 的差值大于 $1$ ，那么不平衡数字加 $1$ ；
如果 $nums[h]$ 存在，并且 $nums[j]$ 与 $nums[h]$ 的差值大于 $1$ ，那么不平衡数字加 $1$ ；
如果 $nums[k]$ 存在，并且 $nums[h]$ 存在，那么将元素 $nums[j]$ 插入 $nums[h]$ 和 $nums[k]$ 的中间，会使得平衡数字减 $1$ 。

然后，我们将当前子数组的平衡数字累加到答案中，继续遍历，直到遍历完所有子数组。

时间复杂度 $O(n^2 \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            sl = SortedList()
            cnt = 0
            for j in range(i, n):
                k = sl.bisect_left(nums[j])
                h = k - 1
                if h >= 0 and nums[j] - sl[h] > 1:
                    cnt += 1
                if k < len(sl) and sl[k] - nums[j] > 1:
                    cnt += 1
                if h >= 0 and k < len(sl) and sl[k] - sl[h] > 1:
                    cnt -= 1
                sl.add(nums[j])
                ans += cnt
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want you to avoid sorting every subarray and instead update the imbalance as the window grows.
question_mark
They expect you to notice that only x-1 and x+1 affect whether a newly added value creates or closes a gap.
question_mark
They may ask why duplicates do not change the imbalance, which tests whether you understand sorted adjacency in this exact problem.

warning

常见陷阱

外企场景

error
Incrementing the imbalance for every unseen value is wrong because inserting x between two existing neighbors should decrease the gap count.
error
Forgetting duplicate handling breaks cases like [1,3,3,3,5], where repeated 3 values should not keep adding imbalance.
error
Recomputing sorted subarrays each time usually leads to an unnecessary O(n^3 log n) style solution that misses the intended local-update pattern.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Replace the hash set with a boolean array because nums[i] is bounded by nums.length, which often simplifies the implementation.
arrow_right_alt
Derive a contribution-based formula that counts how often each value starts a new gap, then subtract overcounted neighbor connections.
arrow_right_alt
Use an ordered set or balanced structure for a more general version where values are not tightly bounded, though it is heavier than needed here.

help

常见问题

外企场景

继续练习

#2713 矩阵中严格递增的单元格数 #3092 最高频率的 ID #2363 合并相似的物品