[Java/C++/Python] Two Loops, O(n)
Solution 1\nEach time, check the array start at A[i],\nand add A[i + 1], A[i + 2] ... one by one.\nAt first, the current imbalance number cur = 0,\nwhen add A[j
# **Solution 1**\nEach time, check the array start at `A[i]`,\nand add `A[i + 1], A[i + 2] ...` one by one.\nAt first, the current imbalance number `cur = 0`,\nwhen add `A[j]`,\ncheck if `A[j] + 1` and `A[j] - 1` already in the subarray.\n\nIf `A[j] + 1` not in `seen` and `A[j] - 1` not in `seen`,\n`A[j]` will make imbalance number increment `cur += 1`.\n\nIf `A[j] + 1` in `seen` and `A[j] - 1` in `seen`,\n`A[j]` will make imbalance number decrement `cur -= 1`.\n\nThen update result with current imbalance number `res += cur`.\n<br>\n\n**Complexity**\nTime `O(n^2)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public int sumImbalanceNumbers(int[] A) {\n        int res = 0, n = A.length;\n        for (int i = 0; i < n; ++i) {\n            Set<Integer> s = new HashSet<>();\n            s.add(A[i]);\n            int cur = 0;\n            for (int j = i + 1; j < n; ++j) {\n                if (!s.contains(A[j])) {\n                    int d = 1;\n                    if (s.contains(A[j] - 1)) d--;\n                    if (s.contains(A[j] + 1)) d--;\n                    cur += d;\n                    s.add(A[j]);\n                }\n                res += cur;\n            }\n        }\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    int sumImbalanceNumbers(vector<int>& A) {\n        int res = 0, n = A.size();\n        for (int i = 0; i < n; ++i) {\n            unordered_set<int> s = {A[i]};\n            int cur = 0;\n            for (int j = i + 1; j < n; ++j) {\n                cur += s.count(A[j]) ? 0 : 1 - s.count(A[j] + 1) - s.count(A[j] - 1);\n                s.insert(A[j]);\n                res += cur;\n            }\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def sumImbalanceNumbers(self, A: List[int]) -> int:\n        n = len(A)\n        res = 0\n        for i in range(n):\n            s = set()\n            cur = -1\n            for j in range(i, n):\n                cur += 0 if A[j] in s else 1 - (A[j] + 1 in s) - (A[j] - 1 in s)\n                s.add(A[j])\n                res += cur\n        return res\n```\n<br>\n\n# **Solution 2**\nFrom solution 1, we know that,\nfor each `A[i]`,\nwe focus if `A[i] + 1` and `A[i] - 1` in the subarray.\n\nIf `A[i]` in the subarray and `A[i] + 1` not,\nit means `A[i]` can contribute one point to imbalance number.\n\nOn this kind of problem,\nwe can check the contribution of each A[i].\nUsually need to find some information, \nlike next bigger on left and right, \nwhich can be solved in O(n).\n\nSo in the first loop,\nwe go through from `A[0]` to `A[n - 1]`,\nand find out the position of `A[i]` or `A[i] + 1` on `A[i]` left.\n\nThen in the second loop,\nwe go through from `A[n - 1]` to `A[0]`,\nand find out the position of `A[i] - 1` on `A[i]` right.\n\nThe valid number of subarray with `A[i]` and without `A[i] + 1`,\nis `(distance on left) * (distance on right)`.\n\nFinally return the sum of contribution for all `A[i]`.\nIn each subarray, the biggest `A[i]` won\'t count score,\nbut we counted its contribution.\nThere are `n * (n + 1) / 2` subarrays,\nso we return `res - n * (n + 1) / 2`.\n<br>\n\n**Complexity**\nTime `O(n)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public int sumImbalanceNumbers(int[] A) {\n        int res = 0, n = A.length;\n        int[] left = new int[n];\n        int[] seen = new int[n + 10];\n        Arrays.fill(seen, -1);\n        for (int i = 0; i < n; i++) {\n            left[i] = Math.max(seen[A[i] + 1], seen[A[i]]);\n            seen[A[i]] = i;\n        }\n        Arrays.fill(seen, n);\n        for (int i = n - 1; i >= 0; i--) {\n            seen[A[i]] = i;\n            res += (i - left[i]) * (seen[A[i] + 1] - i);\n        }\n        return res - n * (n + 1) / 2;\n    }\n```\n\n**C++**\n```cpp\n    int sumImbalanceNumbers(vector<int>& A) {\n        int res = 0, n = A.size();\n        vector<int> left(n), seen(n + 10, -1);\n        for (int i = 0; i < n; i++) {\n            left[i] = max(seen[A[i] + 1], seen[A[i]]);\n            seen[A[i]] = i;\n        }\n        seen.assign(n + 10, n);\n        for (int i = n - 1; i >= 0; i--) {\n            seen[A[i]] = i;\n            res += (i - left[i]) * (seen[A[i] + 1] - i);\n        }\n        return res - n * (n + 1) / 2;\n    }\n```\n\n**Python**\n```py\n    def sumImbalanceNumbers(self, A: List[int]) -> int:\n        n = len(A)\n        left = [0] * n\n        res = 0\n        seen = [-1] * (n + 10)\n        for i in range(n):\n            left[i] = max(seen[A[i] + 1], seen[A[i]])\n            seen[A[i]] = i\n        seen = [n] * (n + 10)\n        for i in range(n - 1, -1, -1):\n            seen[A[i]] = i\n            res += (i - left[i]) * (seen[A[i] + 1] - i)\n        return res - n * (n + 1) // 2\n```\n
['C', 'Python', 'Java']