柳州中小企业网站建设网页设计页面
本文涉及的基础知识点
C++算法：滑动窗口及双指针总结
LeetCode1248. 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 105
1 <= k <= nums.length
滑动窗口
nums[i…j1]包括k个奇数的数字，且j1最小。
nums[i…j2]包括k+1个奇数的数字，且j2最小。
枚举i，ans += j2-j1。此方法称为三指针。
为了简化代码，可以用两个滑动窗口。
一，N-j1，以i开头，包括k个及以上奇数的数目。
二，N-j2，以i开头，包括k+1个及以上奇数的数目。
代码
核心代码
class Solution {public:int numberOfSubarrays(vector<int>& nums, int k) {const int N = nums.size();auto Do = [&](int len) {int cnt = 0;long long res = 0;for (int i = 0, j = 0; i < N; i++) {while ((j < N) && (cnt < len )) {cnt += bool(nums[j] & 1); j++;}if (cnt >= len){res += N - j+1;}cnt -= bool(nums[i] & 1);}return res;};return Do(k) - Do(k + 1);}};
单元测试
vector<int> nums; int k;TEST_METHOD(TestMethod11){nums = { 1,1,2,1,1 },k=3;auto res = Solution().numberOfSubarrays(nums, k);AssertEx(2, res);}TEST_METHOD(TestMethod12){nums = { 2,4,6 }, k = 1;auto res = Solution().numberOfSubarrays(nums, k);AssertEx(0, res);}TEST_METHOD(TestMethod13){nums = { 2,2,2,1,2,2,1,2,2,2 }, k = 2;auto res = Solution().numberOfSubarrays(nums, k);AssertEx(16, res);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
