[930] Binary Subarrays With Sum

其實我真的不是很懂Orz 窗戶怎麼這麼難滑 囧

一樣，來不及了，先背答案再說Orz

說是，要找剛好等於goal 的，沒辦法直接寫，因為如果subarray 有含0的時候，會無法好好的算進去(除非暴力法） 因此神人們都是用 atMost goal 減掉 atMost goal -1

就是=> 要找等於4的subarray，等於 atMost 4 的數目減掉 atMost 3 的數目

那就會是剛好等於4 !!! (WHY!!!不要叫我證明啊啊啊啊啊)

int atMostSum(int* nums, int numsSize, int goal)

{

int l,r,sum,ret;

l=0;

r=0;

sum=0;

ret =0;

while (r < numsSize)

{

sum+=nums[r];

while (l <=r && sum > goal)

{

sum-= nums[l];

l++;

}

ret+=(r-l)+1;

r++;

}

return ret;

}

int numSubarraysWithSum(int* nums, int numsSize, int goal){

return atMostSum(nums, numsSize, goal) -atMostSum(nums, numsSize, goal-1);

}