【C语言刷LeetCode】1248. 统计「优美子数组」(M)

【

给你一个整数数组 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] <= 10^5
1 <= k <= nums.length

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-number-of-nice-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

】

一开始肯定想到的是滑动窗口，但应该会超时，于是想到525这道题525. 连续数组（M)，把奇数偶数转换一下变成0和1，接着发现跟560这道题一模一样了560. 和为 K 的子数组，前缀和+uthash.

ypedef struct {
    int key; // 存放前缀和
    int val; // 存放次数
    UT_hash_handle hh;
} UT_HASH;
 
int numberOfSubarrays(int* nums, int numsSize, int k){
    int ret= 0;
    int i;
    int preSum = 0;
    UT_HASH *hash_table = NULL;
    UT_HASH *tmp = malloc(sizeof(UT_HASH));
    int fkey;
 
    tmp->key = 0;
    tmp->val = 1;
    HASH_ADD_INT(hash_table, key, tmp); // 存入0当首个元素
 
    // 求余2的前缀和
    for (i = 0; i < numsSize; i++) {
        preSum += nums[i] % 2;
 
        fkey = preSum - k;
        tmp = NULL;
        HASH_FIND_INT(hash_table, &fkey, tmp); // 查找 preSum-k，找到了即优美子数组
        if (tmp != NULL) {
            ret += tmp->val;
            printf("h1,i=%d,ret=%d,preSum=%d,tmp->val=%d\n",i,ret,preSum,tmp->val);
        }
 
        tmp = NULL;
        HASH_FIND_INT(hash_table, &preSum, tmp); // 查找自身
        if (tmp != NULL) {
            tmp->val += 1;
        } else {
            UT_HASH *new = malloc(sizeof(UT_HASH));
            new->key = preSum;
            new->val = 1; 
            HASH_ADD_INT(hash_table, key, new); // 没找到就加入
        }
    }
 
    return ret;
}