LeetCode:统计最美子数组

1248. 统计「优美子数组」

给你一个整数数组 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
解释：数列中不包含任何奇数，所以不存在优美子数组。

思路：

构建一个奇数数组，存储原数组中奇数元素的位置。
那么以第i个奇数元素 为第一个奇数元素的 子数组的个数就等于 (第i个奇数元素的下标-第i-1个奇数元素的下标)*(第i+k个奇数元素的下标-第i+k-1个奇数元素的下标).
所有子数组的个数就等于把奇数数组遍历一次所求得的和，当没尚未遍历过的奇数个数小于k时，即可提前终止。

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int num = 0;
        int size = nums.size();
        int *odd = new int[size + 2]; //可能全为奇数，因此要申请size，又因为要加上头尾的边界，故size+2 。奇数元素比较少，元素总量又很多时，用vector会比较好
        memset(odd, 0, sizeof(int)*(size+2));
        int index = 0;
        for (int i = 0; i < size; ++i)
        {
            if (nums[i] & 1)  //快速判断是否为奇数，最后一位和1相与
                odd[++index] = i; //从odd[1]开始
        }
        odd[0] = -1, odd[++index] = size; //边界条件，根据实际加减推出
        for (int i = 1; i + k <= index; ++i) //构造好边界条件，可以统一于循环
        {
            num += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]);
        }
        return num;
    }
};

小知识：

c++中不允许使用变量作为数组的长度定义数组，当长度在运行时才能确定，可以动态申请内存。

Type *p=new Type;
int *p=new int(2);//动态分配一个int的空间并初始化为3

//一维数组申请
Type *p=new Type[n];
int *p=new int[5];
memset(p, 0, sizeof(int)*5); //初始化为0

//二维数组申请p[m][n];
Type **p=new Type*[m];
for(int i=0;i<m;++i)
{
    p[i]=new Type[n];
    memset(p[i], 0, sizeof(int)*n); //初始化为0
}

参考自：<https://blog.csdn.net/weixin_42638401/article/details/88957796>