Quadratic and Linear
We can think of a cubic solution, when, for each i and j, we sort the subarray and compute the imbalance.\n\nWe can then transform it to a quadratic solution, w
We can think of a cubic solution, when, for each `i` and `j`, we sort the subarray and compute the imbalance.\n\nWe can then transform it to a quadratic solution, where we track the current imbalance and adjust it as we include `nums[j]`.\n\nFinally, we can compute how much imbalance is caused by each element (see the second solution below).\n\nThis is similar to [2488. Count Subarrays With Median K](https://leetcode.com/problems/count-subarrays-with-median-k/discuss/2851940/Balance), and we can do it a linear time.\n\n## Quadratic\nEach added number `num[i]` adds `1` to imbalance, and it removes `1` from imbalance if:\n- There is already `nums[i] - 1` in the set.\n- There is already `nums[i] + 1` in the set.\n\nIf both two conditions above are true, then `nums[i]` actually decreases the imbalance by `1`.\n\n**C++**\n```cpp\nint sumImbalanceNumbers(vector<int>& nums) {\n    int res = 0;\n    for (int i = 0; i < nums.size(); ++i) {\n        unordered_set<int> s{nums[i]};\n        for (int j = i + 1, cnt = 0; j < nums.size(); ++j) {\n            auto [it, inserted] = s.insert(nums[j]);\n            if (inserted)\n                cnt += 1 - s.count(nums[j] - 1) - s.count(nums[j] + 1);\n            res += cnt;\n        }\n    }\n    return res;\n}\n```\n\n## Linear\n\nHow much imbalance is added by an element `i`?\n\n- Zero for each subarray that also contains `nums[i] - 1`.\n- One for each subarray that does not contain `nums[i] - 1`.\n\nSo, we count the number of subarrays with `i` that do not contain `nums[i] - 1`.\n\nIn the following example, element `7` adds an imbalance to `4 * 3 = 12` subarrays. As soon as `6` from either side appears in a subarray, `7` stops causing an imbalance.\n\n![image](https://assets.leetcode.com/users/images/074c026b-99f2-4585-b628-a26905ac440a_1688588911.818295.png)\n\nWe use two loops (like in [2488. Count Subarrays With Median K](https://leetcode.com/problems/count-subarrays-with-median-k/discuss/2851940/Balance)) to track the leftmost/rightmost position of each number.\n\nFor `nums[i]`, we use the closest positions of `nums[i] - 1`  for the computation. There are, however, two tricky complications.\n\n**1. Smallest Numbers**\nA number `nums[i]` can be the smallest number in a subarray, and it won\'t cause an imbalance. \n\nIt would be difficult to factor this into our computation logic. Fortunately, there is an easy way.\n\nThere are total `n * (n + 1) / 2` subarrays. In each of those subarrays, the smallest one added `1` to imbalance, and it should not.\n\nTherefore, we just subtract `n * (n + 1) / 2` from the result.\n\n**2. Duplicated Numbers**\nWhat if there is already the same number as `nums[i]` in a subarray? In that case, another `nums[i]` won\'t cause an imbalance.\n\nSo, we use the closest position of either `nums[i]` or `nums[i] - 1` to the left of `i`.\n\nNote that, on the right side, `nums[i]` adds an imbalance even if there is a duplicate on the right (since `nums[i]` is the first occurance).\n\n![image](https://assets.leetcode.com/users/images/25b4f338-7296-4c5d-8377-274e3e67b9fd_1688589942.2731383.png)\n\n**C++**\n```cpp\nint sumImbalanceNumbers(vector<int>& nums) {\n    int res = 0, n = nums.size();\n    vector<int> left, pos(n + 2, -1);\n    for (int i = 0; i < n; ++i) {\n        left.push_back(max(pos[nums[i] - 1], pos[nums[i]]));\n        pos[nums[i]] = i;\n    }\n    fill_n(begin(pos), n + 2, n);\n    for (int i = n - 1; i >= 0; --i) {\n        res += (i - left[i]) * (pos[nums[i] - 1] - i);\n        pos[nums[i]] = i;\n    }\n    return res - n * (n + 1) / 2;\n}\n```
['C']