【C语言刷LeetCode】560. 和为 K 的子数组(M)

【

给你一个整数数组 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

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

】

在2020年7月的时候，这道题暴力能过，但后面就一直超时了。最开始看到要用map，但C语言里面没有这个接口便一直没做，其实UTHASH可以模拟简单map功能。

首先求前缀和su'm，然后找k-sum的个数，并累加，及需要的返回值。然后找自身，找到就加一，没找到便加到哈希里。

// 注：用uthash模拟了一把map功能
typedef struct {
    int key; // key是前缀和
    int val; // val 记录个数
    UT_hash_handle hh;
} UT_HASH;
 
int subarraySum(int* nums, int numsSize, int k){
    int sum = 0;
    int find;
    UT_HASH *hash_table = NULL;
    UT_HASH *tmp = malloc(sizeof(UT_HASH));
    int ret = 0;
 
    tmp->key = 0;
    tmp->val = 1;
    HASH_ADD_INT(hash_table, key, tmp); // 0 需要add 一下
 
    for (int i = 0; i < numsSize; i++) { 
        sum += nums[i]; // 求前缀和，优化到一个for循环里面
        find = sum -k; // 对应需要查找的函数
 
        UT_HASH *fut = NULL;
        HASH_FIND_INT(hash_table, &find, fut); // 查找 sum-k，找到了即满足条件的
        if (fut != NULL) {
            ret += fut->val; 
        }
 
        fut = NULL;
        HASH_FIND_INT(hash_table, &sum, fut); // 寻找自身
        if (fut != NULL) {
            fut->val += 1; // 如果找到了自身，那么val加1，这里模拟的map
        } else {
            fut = malloc(sizeof(UT_HASH));
            fut->key = sum;
            fut->val = 1;
            HASH_ADD_INT(hash_table, key, fut); // 没找到就ADD进哈希表
        }
    }
 
    return ret;
}