สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม nums และจำนวนเต็ม k subarray เรียกว่า nice subarray ถ้ามี k เลขคี่อยู่บนนั้น เราต้องหาจำนวนอาร์เรย์ย่อยที่ดี ดังนั้นหากอาร์เรย์คือ [1,1,2,1,1] และ k =3 ผลลัพธ์จะเป็น 2 เนื่องจากอาร์เรย์ย่อยคือ [1,1,2,1] และ [1,2,1 ,1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ans :=0, n :=ขนาดของอาร์เรย์ nums
- ซ้าย :=0 และขวา :=0 และนับ :=0
- กำหนดอาร์เรย์คี่ เติมค่านี้ด้วยค่าคี่ทั้งหมดที่มีอยู่ใน nums
- ถ้าความยาวของอาร์เรย์คี่คือ>=k แล้ว
- สำหรับฉันคือ 0 และ j ในช่วง k – 1 ถึงขนาดคี่ – 1 เพิ่ม i และ j โดย 1
- ซ้าย :=คี่[i] + 1 ถ้า i =0 มิฉะนั้น คี่[i] – คี่[i – 1]
- ขวา :=คี่[j] ถ้าขนาดของคี่ – 1 =j มิฉะนั้น คี่[j + 1] – คี่[j]
- ans :=ans + ซ้าย * ขวา
- สำหรับฉันคือ 0 และ j ในช่วง k – 1 ถึงขนาดคี่ – 1 เพิ่ม i และ j โดย 1
- คืนสินค้า
ตัวอย่าง(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();
int left = 0;
int right = 0;
int cnt = 0;
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;
}
};
main(){
vector<int> v = {1,1,2,1,1};
Solution ob;
cout <<ob.numberOfSubarrays(v, 3);
} อินพุต
[1,1,2,1,1] 3
ผลลัพธ์
2
