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

链接：2763.所有子数组中不平衡数字之和
难度：Hard
标签：数组、哈希表、有序集合
简介：给你一个下标从 0 开始的整数数组 nums ，请你返回它所有 子数组 的 不平衡数字 之和。

题解 1 - cpp

• 编辑时间：2023-07-02
• 执行用时：816ms
• 内存消耗：137.5MB
• 编程语言：cpp
• 解法介绍：平衡树。

class Solution {
public:
    int sumImbalanceNumbers(vector<int>& nums) {
        int n = nums.size(), res = 0;
        for (int i = 1; i < n; i++) {
            map<int, int> m;
            int cnt = 0;
            for (int j = i; j >= 0; j--) {
                m[nums[j]]++;
                if (m[nums[j]] > 1) {
                    res += cnt;
                    continue;
                }
                auto it = m.find(nums[j]);
                auto prev = it;
                if (prev != m.begin()) {
                    prev--;
                    if (nums[j] - prev->first > 1) cnt++;
                }
                auto next = it;
                next++;
                if (next != m.end()) {
                    if (next->first - nums[j] > 1) cnt++;
                }
                if (it != m.begin() && next != m.end()) cnt--;
                res += cnt;
            }
        }
        return res;
    }
};