题目描述
给你一个整数数组 nums
和一个整数 k
。
如果某个子数组中恰好有 k
个奇数数字,我们就认为这个子数组是优美子数组。
请返回这个数组中优美子数组的数目。
样例
输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。
输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16
限制
1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length
算法1
(二分查找) $O(n \log n)$
- 统计出每个位置和之前有多少奇数的前缀和数组
sum
。 - 对于每个位置
i
,二分出两个最大的位置p1
和p2
,满足[p1, i]
有k
个奇数,[p2, i]
有k + 1
个奇数。则这个位置贡献的答案就是p1 - p2
。
时间复杂度
- 每个位置需要 $O(\log n)$ 的时间复杂度,故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要额外 $O(n)$ 的空间求前缀和。
C++ 代码
class Solution {
public:
int find(const vector<int>& sum, int i, int k) {
int l = 0, r = i;
while (l < r) {
int mid = (l + r) / 2;
if (sum[i] - sum[mid] >= k)
l = mid + 1;
else
r = mid;
}
return l;
}
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> sum(n + 1, 0);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + nums[i - 1] % 2;
int ans = 0;
for (int i = 1; i <= n; i++)
ans += find(sum, i, k) - find(sum, i, k + 1);
return ans;
}
};
算法2
(双指针) $O(n)$
- 算法 1 中每次都重新二分查找显然是冗余的,对于每个位置我们可以每次均摊常数的时间维护出有恰好
k
个奇数的区间长度。 - 双指针扫描
i
在前,j
在后。 - 如果当前位置是奇数,则更新计数器,如果当前
[j, i]
有了恰好k
个奇数,则移动j
直到不满足,期间统计出长度为tot
。让ans
累加tot
。 - 如果当前位置是偶数,则说明贡献的答案和上一次是奇数的时候一样,直接让
ans
累加上一次的tot
。
时间复杂度
- 每个位置最多遍历两次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int cnt = 0, tot = 0, ans = 0;
for (int i = 0, j = 0; i < n; i++) {
if (nums[i] % 2 == 1) {
cnt++;
if (cnt == k)
tot = 0;
while (cnt == k) {
tot++;
if (nums[j] % 2 == 1)
cnt--;
j++;
}
}
ans += tot;
}
return ans;
}
};
算法3
(组合数学) $O(n)$
- 算法 2 中的过程可以进一步优化。
- 我们用一个数组统计出奇数的位置,头和尾加入
-1
和n
两个哨兵位置。 - 在奇数数组中,对于每连续
k
个奇数区间[i, j]
,其贡献的答案就是(s[i] - s[i - 1]) * (s[i + k] - s[i + k - 1])
。
时间复杂度
- 扫两遍数组,时间复杂度为 $O(n)$。
空间复杂度
- 需要额外的数组记录奇数的位置,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> s;
s.push_back(-1);
for (int i = 0; i < n; i++)
if (nums[i] & 1)
s.push_back(i);
s.push_back(n);
int ans = 0;
for (int i = 1; i + k < s.size(); i++)
ans += (s[i] - s[i - 1]) * (s[i + k] - s[i + k - 1]);
return ans;
}
};
这题神似LeetCode992题,可能大佬自己都忘了自己写过另一种双指针算法,我来补一个
tot 命名是什么的缩写吗??谢谢
total
好的~谢谢~
是真滴强