C++ Prefix State Map / Two Pointers / Sliding Window
See my latest update in repo LeetCode\n\n## Solution 1. Prefix State Map\n\nUse a map m to store the mapping from the count of odd numbers cnt to the first inde
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Prefix State Map\n\nUse a map `m` to store the mapping from the count of odd numbers `cnt` to the first index in the array that has `cnt` numbers in front of it and including itself.\n\nWhen `cnt >= k`, we add `m[cnt - k + 1] - m[cnt - k]` to the answer.\n\n```cpp\n// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(N)\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& A, int k) {\n        int N = A.size(), cnt = 0, ans = 0;\n        unordered_map<int, int> m{{0,-1}};\n        for (int i = 0; i < N; ++i) {\n            cnt += A[i] % 2;\n            if (m.count(cnt) == 0) m[cnt] = i;\n            if (cnt >= k) ans += m[cnt - k + 1] - m[cnt - k]; \n        }\n        return ans;\n    }\n};\n```\n\n## Solution 2. Two Pointers\n\nAssume the current pointer is `j` and the corresponding odd number count is `cj`, we need two pointers to get the answer.\n\nThe first pointer `i` is the index whose corresponding odd number count is `cj - k + 1`.\n\nThe second pointer `prev` is the index whose corresponding odd number count is `cj - k`.\n\nSo when `cj >= k`, we add `i - prev` to the answer.\n\n```cpp\n// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& A, int k) {\n        int N = A.size(), i = 0, j = 0, prev = -1, ans = 0, ci = 0, cj = 0;\n        while (j < N) {\n            cj += A[j++] % 2;\n            if (ci <= cj - k) {\n                prev = i;\n                while (ci <= cj - k) ci += A[i++] % 2;\n            }\n            if (cj >= k) ans += i - prev;\n        }\n        return ans;\n    }\n};\n```\n\nOr use a single count.\n\n```cpp\n// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& A, int k) {\n        int N = A.size(), i = 0, j = 0, prev = -1, ans = 0, cnt = 0;\n        while (j < N) {\n            int c = A[j++] % 2;\n            cnt += c;\n            if (c && cnt >= k) {\n                prev = i;\n                while (A[i] % 2 == 0) ++i;\n                ++i;\n            }\n            if (cnt >= k) ans += i - prev;\n        }\n        return ans;\n    }\n};\n```\n\n## Solution 3. AtMost to Equal\n\nCheck out "[C++ Maximum Sliding Window Cheatsheet Template!](https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1175088/C%2B%2B-Maximum-Sliding-Window-Cheatsheet-Template!)"\n\nExactly `k` times = At Most `k` times - At Most `k - 1` times.\n\n```cpp\n// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\n// Ref: https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419378/JavaC%2B%2BPython-Sliding-Window-O(1)-Space\nclass Solution {\n    int atMost(vector<int> &A, int k) {\n        int N = A.size(), i = 0, ans = 0;\n        for (int j = 0; j < N; ++j) {\n            k -= A[j] % 2;\n            while (k < 0) k += A[i++] % 2;\n            ans += j - i;\n        }\n        return ans;\n    }\npublic:\n    int numberOfSubarrays(vector<int>& A, int k) {\n        return atMost(A, k) - atMost(A, k - 1);\n    }\n};\n```
[]