560. 和为 K 的子数组【哈希、前缀和】-Toy模板网

这篇具有很好参考价值的文章主要介绍了560. 和为 K 的子数组【哈希、前缀和】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

C代码：哈希、前缀和

560. 和为 K 的子数组【哈希、前缀和】

只需要统计有多少个前缀和 == sum - k
把移动的滑动窗口的问题转换为 不断变换的前缀和的问题
【模型想象】：滑动窗口的和不变，随着滑动窗口右端向右移动的同时，窗口为满足sum一定，左端会做出对应的响应；此时，就将 总前缀和 ([0, i]的和pre[i]) - k 的问题转换为 pre[j-1]前缀和 的问题；
（每次滑动窗口均不一致，就算是每次窗口使用的都是相同的前缀和，此时的窗口也是不一致的。例如：1 2 3 0 0 k==3）

typedef struct hashNode {
    int prefixSum;
    int cnt;
    UT_hash_handle hh;
} HashNode;

int subarraySum(int* nums, int numsSize, int k)
{
    int cnt = 0;
    HashNode *hashSet = NULL;
    int prefixSum = 0;

    HashNode *head = (HashNode *)malloc(sizeof(HashNode));
    head->prefixSum = 0;
    head->cnt = 1;
    HASH_ADD_INT(hashSet, prefixSum, head);

    for (int i = 0; i < numsSize; i++) {
        prefixSum += nums[i];
        int value = prefixSum - k;
        HASH_FIND_INT(hashSet, &value, head);
        if (head != NULL) {
            cnt += head->cnt;
        }

        HASH_FIND_INT(hashSet, &prefixSum, head);
        if (head != NULL) {
            head->cnt++;
        } else {
            head = (HashNode *)malloc(sizeof(HashNode));
            head->prefixSum = prefixSum;
            head->cnt = 1;
            HASH_ADD_INT(hashSet, prefixSum, head);
        }
    }
    return cnt;
}

C代码：暴力、超过时间限制

int subarraySum(int* nums, int numsSize, int k){
    int cnt = 0;
    for (int i = 0; i < numsSize; ++i) {
        int sum = 0;                          // 包含负数、0
        for (int j = i; j < numsSize; ++j) {  // for遍历就包含了顺序：滑动窗口
            sum += nums[j];
            if (sum == k) {
                ++cnt;
            }
        }
    }
    return cnt;
}

C错误代码：滑动窗口没有考虑到负数和0文章来源地址https://www.toymoban.com/news/detail-434266.html

int subarraySum(int* nums, int numsSize, int k){
    int sum = 0;
    int cnt = 0;
    int l = 0;
    for (int i = 0; i < numsSize; ++i) {
        sum += nums[i];
        while(sum > k) {  // 没有考虑到负数和0
            sum -= nums[l];
            ++l;
        }
        if (sum == k) {
            ++cnt;
        }
    }
    return cnt;
}