對抗惰性家淤，從今天做起异剥。堅持每天刷leetcode并附帶一個題的題目，思路絮重，代碼冤寿。感興趣的小伙伴一起堅持來吧(c代碼，不過思路都是差不多的)青伤。
題目(難度中等):
給出一個數(shù)組督怜，元素為非負的。并給出一個整數(shù)k狠角，檢查數(shù)組中有沒有連續(xù)的并且長度大于等于2的子數(shù)組求和為k的整數(shù)倍号杠。并返回有沒有這樣的子數(shù)組。
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
思路：
這幾天做的都是動態(tài)規(guī)劃丰歌，今天這個題我想到的思路的時間復雜度最小也是數(shù)組長度的平方（不過打敗了百分之七十多的提交者）姨蟋。既然要用動態(tài)規(guī)劃，先看一下哪些地方會有重復運算現(xiàn)象進而可以改進立帖。很明顯芬探，一個比較長的子數(shù)組的和可以由比它長度小一的子數(shù)組的和加上一個元素得到。
這樣厘惦，我們就有了初步思路偷仿，長度為1的數(shù)組有n個，長度為2的數(shù)組有n-1個...這樣可以用一個二維數(shù)組存儲這些求和宵蕉，在求長度為x的數(shù)組的和的時候酝静，可以用到長度為x-1的數(shù)組的和，再加上一個數(shù)就能求出結(jié)果羡玛。
但是别智，空間能不能再小一些呢，像我之前寫過的最大股票利潤里面也有一個類似的例子稼稿。就是用長度為x的數(shù)組的和的數(shù)據(jù)時薄榛，前面的數(shù)據(jù)已經(jīng)不需要了讳窟。所以我門可以只用一個一維數(shù)組，每次更新敞恋，前面不用的數(shù)據(jù)直接被取代就行了丽啡。
最后，除了核心的思路：
k可以是0坝裁ā２构俊！Ｐッ邸坑雅！
你考慮了？k是0直接返回不能衬横？數(shù)組元素可以都是0肮痢！７淞帧蛹尝！
什么？你還考慮了悉尾？數(shù)組元素可以只有1個0啊（題目要求長度大于等于2）４炷稹９姑小！
哈哈哈哈Ｔ绻辍１拱浴！
好了葱弟，上代碼
代碼：
bool checkSubarraySum(int* nums, int numsSize, int k) {
int i = 0, j = 0;
if(k==0)
{
if(numsSize==1)
return 0;
for(i=0;i<numsSize;i++)
{
if(nums[i]!=0)
return 0;
}
return 1;
}
int* sum = malloc(sizeof(int)*numsSize);
if(numsSize>1)
{
for(j=0;j<numsSize-1;j++)
{
sum[j] = nums[j]+nums[j+1];
if((sum[j]%k)==0)
return 1;
}
}
for(i=2;i<numsSize;i++)
{
for(j=0;j<numsSize-i;j++)
{
sum[j] = sum[j]+nums[j+i];
if((sum[j]%k)==0)
return 1;
}
}
return 0;
}
