Hard

题目描述

长度为 n 的 0 索引 整数数组 arr 的 不平衡数字 定义为满足以下条件的下标数量：

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

这里，sorted(arr) 是将数组 arr 排序后的结果。

给你一个 0 索引 的整数数组 nums，请你返回它所有 子数组 的 不平衡数字 之和。

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

示例 1：

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

示例 2：

输入：nums = [1,3,3,3,5]
输出：8
解释：有 7 个子数组有非零不平衡数字：
- 子数组 [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

解题思路

解题思路

这道题需要计算所有子数组的不平衡数字之和。不平衡数字是指排序后相邻元素差值大于1的位置数量。

暴力解法思路： 最直接的方法是枚举所有子数组，对每个子数组排序并计算不平衡数字。时间复杂度为O(n³logn)，对于n=1000的数据规模可能会超时。

优化解法思路： 我们可以采用动态维护的方法来优化。对于每个左端点，我们逐步扩展右端点，并动态维护当前子数组的不平衡数字：

  1. 使用集合维护当前子数组中的唯一元素
  2. 当添加新元素时，根据以下规则更新不平衡数字：
    • 如果新元素是最大值或最小值，且与相邻值差值>1，则增加不平衡数字
    • 如果新元素填补了两个相邻值之间的空隙（差值>2），则减少不平衡数字
    • 如果新元素介于两个值之间但都不相邻，则不平衡数字增加1

核心观察：

  • 新加入的数字如果与现有数字不相邻（差值>1），会增加不平衡数字
  • 新加入的数字如果同时与两个现有数字相邻，会减少不平衡数字
  • 重复数字不会改变不平衡数字

这种方法的时间复杂度为O(n²)，空间复杂度为O(n)，可以有效解决该问题。

代码实现

class Solution {
public:
    int sumImbalanceNumbers(vector<int>& nums) {
        int n = nums.size();
        int totalSum = 0;
        
        for (int left = 0; left < n; left++) {
            set<int> seen;
            int imbalance = 0;
            
            for (int right = left; right < n; right++) {
                int num = nums[right];
                
                if (seen.find(num) == seen.end()) {
                    seen.insert(num);
                    
                    bool hasLower = seen.find(num - 1) != seen.end();
                    bool hasUpper = seen.find(num + 1) != seen.end();
                    
                    if (hasLower && hasUpper) {
                        imbalance--;
                    } else if (!hasLower && !hasUpper && seen.size() > 1) {
                        imbalance++;
                    }
                }
                
                totalSum += imbalance;
            }
        }
        
        return totalSum;
    }
};

class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = 0
        
        for left in range(n):
            seen = set()
            imbalance = 0
            
            for right in range(left, n):
                num = nums[right]
                
                if num not in seen:
                    seen.add(num)
                    
                    has_lower = (num - 1) in seen
                    has_upper = (num + 1) in seen
                    
                    if has_lower and has_upper:
                        imbalance -= 1
                    elif not has_lower and not has_upper and len(seen) > 1:
                        imbalance += 1
                
                total_sum += imbalance
        
        return total_sum

public class Solution {
    public int SumImbalanceNumbers(int[] nums) {
        int n = nums.Length;
        int totalSum = 0;
        
        for (int left = 0; left < n; left++) {
            HashSet<int> seen = new HashSet<int>();
            int imbalance = 0;
            
            for (int right = left; right < n; right++) {
                int num = nums[right];
                
                if (!seen.Contains(num)) {
                    seen.Add(num);
                    
                    bool hasLower = seen.Contains(num - 1);
                    bool hasUpper = seen.Contains(num + 1);
                    
                    if (hasLower && hasUpper) {
                        imbalance--;
                    } else if (!hasLower && !hasUpper && seen.Count > 1) {
                        imbalance++;
                    }
                }
                
                totalSum += imbalance;
            }
        }
        
        return totalSum;
    }
}

var sumImbalanceNumbers = function(nums) {
    const n = nums.length;
    let totalSum = 0;
    
    for (let left = 0; left < n; left++) {
        const seen = new Set();
        let imbalance = 0;
        
        for (let right = left; right < n; right++) {
            const num = nums[right];
            
            if (!seen.has(num)) {
                seen.add(num);
                
                const hasLower = seen.has(num - 1);
                const hasUpper = seen.has(num + 1);
                
                if (hasLower && hasUpper) {
                    imbalance--;
                } else if (!hasLower && !hasUpper && seen.size > 1) {
                    imbalance++;
                }
            }
            
            totalSum += imbalance;
        }
    }
    
    return totalSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双重循环枚举所有子数组，集合操作为O(1)
空间复杂度O(n)使用集合存储当前子数组中的唯一元素

相关题目