Đếm mảng con đẹp trong C++

Cho mảng nums và số nguyên k. Mảng con "đẹp" là mảng con chứa đúng k số lẻ. Đếm số mảng con đẹp.

Ví dụ: [1,1,2,1,1], k=3 → Kết quả: 2. Các mảng con: [1,1,2,1] và [1,2,1,1].

Giải thuật (Vị trí số lẻ)

1. Lưu vị trí các số lẻ vào mảng odd.
2. Nếu odd.size() < k, trả về 0.
3. Duyệt cửa sổ k số lẻ liên tiếp: với cặp (i, j) (j = i+k-1):
4. left = số vị trí có thể mở rộng về trái: i==0 ? odd[i]+1 : odd[i]-odd[i-1].
5. right = số vị trí mở rộng về phải: j==odd.size()-1 ? n-odd[j] : odd[j+1]-odd[j].
6. Cộng left * right vào kết quả.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int ans = 0, n = nums.size();
        vector<int> odd;
        for(int i = 0; i < n; i++) if(nums[i] % 2 == 1) odd.push_back(i);
        if(odd.size() >= k) {
            for(int i = 0, j = k-1; j < odd.size(); i++, j++) {
                int left = (i == 0) ? odd[i] + 1 : odd[i] - odd[i-1];
                int right = (j == odd.size()-1) ? n - odd[j] : odd[j+1] - odd[j];
                ans += left * right;
            }
        }
        return ans;
    }
};

int main() {
    vector<int> v = {1,1,2,1,1};
    Solution ob;
    cout << ob.numberOfSubarrays(v, 3);
    return 0;
}

Đầu vào

[1,1,2,1,1] 3

Đầu ra

2