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

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

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

这里，sorted(arr) 表示将数组 arr 排序后得到的数组。
给你一个下标从 0 开始的整数数组 nums ，请你返回它所有子数组的不平衡数字之和。

1. 哈希

class Solution {
public:
    int sumImbalanceNumbers(vector<int> &nums) {
        int ans = 0, n = nums.size();
        bool vis[n + 2]; //注意这里数据大小小于长度，使用哈希代替排序，因为只需判断相邻
        for (int i = 0; i < n; i++) { //以i为左边界
            memset(vis, 0, sizeof(vis)); //重置
            vis[nums[i]] = true;
            int cnt = 0; //记录当前数组不平衡数
            for (int j = i + 1; j < n; j++) { //以j为右边界
                int x = nums[j];
                if (!vis[x]) { //更改当前不平衡数，重复数不记
                    cnt += 1 - vis[x - 1] - vis[x + 1];
                    vis[x] = true;
                }
                ans += cnt; //累加
            }
        }
        return ans;
    }
};

2. 贡献法

class Solution {
public:
    int sumImbalanceNumbers(vector<int> &nums) {
        int n = nums.size(), right[n], idx[n + 1];
        fill(idx, idx + n + 1, n); //初始右侧边界下标默认为n
        for (int i = n - 1; i >= 0; i--) {//从右往左遍历，记录右侧
            int x = nums[i];
            // right[i] 表示 nums[i] 右侧的 x 和 x-1 的最近下标（不存在时为 n）
            right[i] = min(idx[x], idx[x - 1]);
            idx[x] = i;
        }
        //x作为不平衡数字的贡献值的数组
        int ans = 0;
        memset(idx, -1, sizeof(idx)); //重置下标，左侧边界下标默认为-1
        for (int i = 0; i < n; i++) {//枚举以i为
            int x = nums[i];
            // 统计 x 能产生多少贡献
            ans += (i - idx[x - 1]) * (right[i] - i); // 子数组左端点个数 * 子数组右端点个数
            idx[x] = i;
        }
        // 上面计算的时候，每个子数组的最小值必然可以作为贡献，而这是不合法的
        // 所以每个子数组都多算了 1 个不合法的贡献
        return ans - n * (n + 1) / 2;
    }
};