[560] Subarray Sum Equals K

ㄜ.........暴力法先放一版？！（當然超時XD）

一開始沒發現它可能有負數，還很開心的sorting  XD

真是太天真了啊～～～～（搖食指）

int subarraySum(int* nums, int numsSize, int k){

int count=0;

int tmpsum=0;

for (int i=0;i<numsSize-1; i++)

{

tmpsum=nums[i];

if (tmpsum==k)

{

count++;

}

for (int j=i+1;j<numsSize; j++)

{

tmpsum+=nums[j];

if (tmpsum==k)

{

count++;

// break;

}

}

}

if (nums[numsSize-1]==k)

count++;

return count;

}

用prefix sum 也是會超時... (奇怪別人不會嗎XD）

因為用C寫hashmap太麻煩了(?) 不用hash map的解答又看不懂 （？）

int subarraySum(int* nums, int numsSize, int k){

int count=0;

int *presum=calloc(numsSize, sizeof(int));

presum[0]=nums[0];

for (int i=1;i<numsSize; i++)

{

presum[i]=nums[i]+presum[i-1];

}

for (int i=0;i<numsSize; i++)

{

if(presum[i]==k)

count++;

for (int j=i+1;j<numsSize; j++)

{

if (presum[j]-presum[i]==k)

count++;

}

}

return count;

}

最後終於弄懂了Orz 用hash 去記錄答案曾經出現過的次數，

之後sum -k 等於hash裡的某個index值那表示它的次數要被算進去

看了這裡以後就懂了!

https://medium.com/@ChYuan/leetcode-560-subarray-sum-equals-k-%E5%BF%83%E5%BE%97-medium-174f3c9edc5c

而因為輸入值有負數，所以偷吃步把它們平移！！！XD

正規解應該是要去弄linked list 長hash裡從有index跟presum或自己的value 之類的吧總而言之姆襪哈哈哈哈哈!!!!!!

int subarraySum(int* nums, int numsSize, int k){

int count=0;

int rebase = numsSize * 1000;

int *hash=calloc(2*rebase+1, sizeof(int));

hash[rebase]++;

int sum=0;

for (int i=0; i<numsSize;i++)

{

sum+=nums[i];

count+= hash[sum+rebase-k];

hash[sum+rebase]++;

}

return count;

}