[C++, Java, Python3] Simple HashSet Solution
\n# Intuition\n\nO(n^3) solution is trivial. We can use a hashset to reduce time complexity from O(n^3) to O(n^2).\n\n# Approach\n\n1. Iterate over each element
\n# Intuition\n\n`O(n^3)` solution is trivial. We can use a hashset to reduce time complexity from `O(n^3)` to `O(n^2)`.\n\n# Approach\n\n1. Iterate over each element in the input array, determining the starting point of the subarray.\n2. Within each subarray, track unique elements encountered and maintain a variable to count the imbalance numbers.\n3. While iterating over the elements in each subarray, update the imbalance number based on the following conditions:\n\n   a. If the current element `x` is already present in the set of unique elements `s`, it means `x` has been encountered before in the subarray. In this case, do nothing and proceed to the next element.\n\n   b. If `x` is not present in `s`, check two conditions to determine whether to update the imbalance number:\n    - If both `x - 1` and `x + 1` are present in `s`, it implies that the sorted order will not have a gap greater than one between `x - 1` and `x + 1`. Therefore, the current element `x` does not contribute to the imbalance number. In this case, decrement the `curr` variable by one.\n\n    - If neither `x - 1` nor `x + 1` is present in `s` and the set `s` is not empty (indicating that `x` is not the first element encountered in the subarray), the current element `x` adds to the imbalance number. Therefore, increment the `curr` variable by one.\n\n4. Accumulate the imbalance numbers of all subarrays and return the total sum as the final result.\n\n# Complexity\n- Time complexity: `O(n^2)`\n\n- Space complexity: `O(n)`\n\n# Code\n\n**Python3**:\n```\ndef sumImbalanceNumbers(self, nums):\n    n = len(nums)\n    ans = 0\n    for i in range(n):\n        s = set()\n        curr = 0\n        for x in nums[i:]:\n            if x in s: \n                pass\n            elif (x - 1 in s) and (x + 1 in s):\n                curr -= 1\n            elif (x - 1 not in s) and (x + 1 not in s) and s:\n                curr += 1\n            s.add(x)\n            ans += curr\n    return ans\n```\n\n**C++**:\n```\n    int sumImbalanceNumbers(vector<int>& nums) {\n        int n = nums.size();\n        int ans = 0;\n        for (int i = 0; i < n; i++) {\n            unordered_set<int> s;\n            int curr = 0;\n            for (int j = i; j < n; j++) {\n                int x = nums[j];\n                if (s.count(x)) {\n                    // do nothing\n                } else if (s.count(x - 1) && s.count(x + 1)) {\n                    curr--;\n                } else if (!s.count(x - 1) && !s.count(x + 1) && !s.empty()) {\n                    curr++;\n                }\n                s.insert(x);\n                ans += curr;\n            }\n        }\n        return ans;\n    }\n```\n\n**Java**:\n```\npublic int sumImbalanceNumbers(int[] nums) {\n    int n = nums.length;\n    int ans = 0;\n    for (int i = 0; i < n; i++) {\n        Set<Integer> s = new HashSet<>();\n        int curr = 0;\n        for (int j = i; j < n; j++) {\n            int x = nums[j];\n            if (s.contains(x)) {\n                // do nothing\n            } else if (s.contains(x - 1) && s.contains(x + 1)) {\n                curr--;\n            } else if (!s.contains(x - 1) && !s.contains(x + 1) && !s.isEmpty()) {\n                curr++;\n            }\n            s.add(x);\n            ans += curr;\n        }\n    }\n    return ans;\n}\n```\n
['C++', 'Java', 'Python3']