先求取nums中奇数个数的前缀和arr
,即arr[i]
表示nums
数组中前i
个数有多少个奇数。
则对于每一个子数组nums[i...j]
,其中的奇数个数可以采用arr[j]-arr[i-1]
求得。
则问题转换成有多少个数对(i,j)
,其中arr[j]-arr[i] = k
,这就是我们喜闻乐见的two sum问题啦,用hash
表即可O(n)
解决
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> arr;
arr.push_back(0);
for(auto x:nums) arr.push_back(arr.back() + (x&1));
unordered_map<int,int> h;
int ans = 0;
for(auto x:arr) {
ans += h[x-k];
h[x] ++;
}
return ans;
}
};
如果把两次遍历写到一起,再考虑到数据范围只有$10^5$,可以用数组代替unordered_map
,得到一个大概可以说是跑的飞快的版本了
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
static int h[100010];
memset(h,0,sizeof(h));
h[0] = 1;
int cnt = 0;
int ans = 0;
for(auto x:nums) {
if(x&1) cnt++;
if(cnt>=k)
ans += h[cnt-k];
h[cnt] ++;
}
return ans;
}
};
这部分有点疑惑,可以讲一讲么?
h[x-k]代表前缀和里面h[x-k]有多少个。有多少个就有多少对(i,j)使得x-(x-k)=k,答案就加几就可以了。如果做过two sum那题的hash解法的话应该会容易理解这里
妙啊!懂了,谢谢大佬。