C++ Subtract Bad Pairs
Intuition\n Describe your first thoughts on how to solve this problem. \nFor each subarray, we can count the number of pairs that do not satisfy the condition a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor each subarray, we can count the number of pairs that do not satisfy the condition and subtract it from the total number of pairs. Each pair can be identified by the last of the two values to appear. \n\n# Approach\n\nFor each subarray starting point we iterate through all possible ending points from left to right, maintaining the current number of "bad pairs" and subtracting it from the total number of pairs. We use a set of seen values for each starting point to count pairs.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    int sumImbalanceNumbers(vector<int>& nums) {\n        int n = nums.size();\n\n        int ret = 0;\n\n        for (int i = 0; i < n; i++) {\n            vector<int> count(n + 2, 0);\n            int prev = 0;\n            for (int j = i; j < n; j++) {\n                int lessPairs = 0;\n\n                if (count[nums[j]] > 0) {\n                    lessPairs++;\n                } else {\n                    if (count[nums[j] - 1]) {\n                        lessPairs++;\n                    }\n\n                    if (count[nums[j] + 1]) {\n                        lessPairs++;\n                    }\n                }\n\n                ret += (j - i - (lessPairs + prev));\n\n                prev += lessPairs;\n\n                count[nums[j]] = 1;\n            }\n        }\n\n        return ret;\n    }\n};\n```
['C++']