和为K的子数组(Subarray Sum Equals K)

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

int subarraySum(int* nums, int numsSize, int k){
    int count = 0;
    for(int i =0;i<numsSize;i++){
        int sum = 0;
        for(int j=i;j<numsSize;j++){
            sum+=nums[j];
            if(sum == k){
                count++;
            }
        }
    }
    return count;
}

O(n^2) 会超时哦

int subarraySum(int* nums, int numsSize, int k){
    int sum[numsSize+1];
    sum[0] = 0;
    for(int i =0;i<numsSize;i++){
        sum[i+1] = sum[i]+nums[i];
    }
    int count = 0;
    for(int j =0;j<numsSize;j++){
        int target = sum[j+1]-k;
        for(int i=0;i<=j;i++){
            if(sum[i] == target){
                count++;
            }
        }
    }
    return count;
}

因为还是O(n^2),但是我这段是抄别人的？为什么也超时了，明明视频里没超时，更新测试样例了？必须要O(n) 的时间复杂度了吗？还是超时了…

int CAPACITY = 1000000;

struct Entry{
    int sum;
    int count;
};

int getIndex(int sum){
    // 为了保证是正的
    return (sum % CAPACITY + CAPACITY)%CAPACITY;
}

void addOne(struct Entry** counter, int sum) {
    int i = getIndex(sum);
    while (counter[i] != NULL) {
        if(counter[i]->sum == sum){
            counter[i]->count++;
            return;
        }
        i = getIndex(i+1);
    }
    struct Entry* entry = malloc(sizeof(struct Entry));
    entry->sum = sum;
    entry->count = 1;
    counter[i] = entry;
}

int query(struct Entry** counter, int sum){
    int i = getIndex(sum);
    while (counter[i] != NULL) {
        if(counter[i]->sum == sum){
            return counter[i]->count;
        }
        i = getIndex(i+1);
    }
    return 0;
}

int subarraySum(int* nums, int numsSize, int k){
    struct Entry** counter = calloc(CAPACITY, sizeof(struct Entry*));

    int sum = 0;
    int totalCount = 0;
    for(int j =0;j<numsSize;j++){
        addOne(counter, sum);
        sum += nums[j];
        int target = sum - k;
        totalCount += query(counter, target);
    }
    free(counter);
    return totalCount;
}

最后的free其实也有点问题，没有一个一个free,理论上需要把counter里面的每一个元素都free，然后再free counter才完整

这题最后是自己手动实现了一个hashTable