นับจำนวนซับอาร์เรย์ที่ดีใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม nums และจำนวนเต็ม k ซับอาร์เรย์เรียกว่า "ดี" (nice) ถ้ามีจำนวนคี่เท่ากับ k ต้องการหาจำนวนซับอาร์เรย์ที่ดี

ตัวอย่าง: [1,1,2,1,1], k = 3 ผลลัพธ์: 2 ซับอาร์เรย์คือ [1,1,2,1] และ [1,2,1,1]

ขั้นตอนการแก้ปัญหา (ตำแหน่งของเลขคี่)

• ans := 0, n := ขนาดของ nums
• เก็บดัชนีของเลขคี่ทั้งหมดไว้ในอาร์เรย์ odd
• ถ้า ขนาดของ odd >= k:
  • วนลูป i = 0, j = k-1 ถึง ขนาดของ odd - 1 เพิ่ม i, j ทีละ 1:
    • left := odd[i] + 1 ถ้า i = 0 มิฉะนั้น odd[i] - odd[i-1]
    • right := n - odd[j] ถ้า j = ขนาดของ odd - 1 มิฉะนั้น odd[j+1] - odd[j]
    • ans := ans + left * right
• คืนค่า ans

ตัวอย่างโค้ด (C++)

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

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int ans = 0;
        int 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);
}

อินพุต

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

เอาต์พุต

2