0560-subarray-sum-equals-k.c

#defineINIT_HASH_SIZE 4096

// Represent an element in a hash table.
typedefstructHash {
intkey;
intcount;
structHash*next;
} Hash;

Hash*InitHash() {
Hash*h= (Hash*)calloc(INIT_HASH_SIZE, sizeof(Hash));
assert(h);
returnh;
}

Hash*NewHash(intkey) {
Hash*h= (Hash*)malloc(sizeof(Hash));
assert(h);
h->key=key;
h->count=1;
h->next=NULL;
returnh;
}

intHashKey(intkey) {
while(key<0) key+=INIT_HASH_SIZE;
return (key % INIT_HASH_SIZE);
}

voidAddHash(Hash*root, intkey) {
assert(root);
Hash*h=&root[HashKey(key)];
if (h->key==0&&h->count==0) {
h->key=key;
h->count=1;
 } elseif (h->key==key) {
h->count++;
 } else {
while (h) {
if (h->key==key) {
h->count++;
return;
 } elseif (!h->next) {
h->next=NewHash(key);
return;
 }
h=h->next;
 }
 }
}

// If hash not round return 0 on purpose.
intGetHash(Hash*root, intkey) {
Hash*h=&root[HashKey(key)];
while(h) {
if (h->key==key) {
returnh->count;
 }
h=h->next;
 }
return0;
}

intsubarraySum(int*nums, intnumsSize, intk){
Hash*hash=InitHash();
intsum=0;
intres=0;
intr=0;

AddHash(hash, 0);
for(inti=0; i<numsSize; i++){
sum+=nums[i];
res+=GetHash(hash, sum-k);
AddHash(hash, sum);
 }

returnres;
}