跟我坚持刷leetcode（第六天-连续子数组的和）

对抗惰性，从今天做起。坚持每天刷leetcode并附带一个题的题目，思路，代码。感兴趣的小伙伴一起坚持来吧(c代码，不过思路都是差不多的)。

题目(难度中等):
给出一个数组，元素为非负的。并给出一个整数k，检查数组中有没有连续的并且长度大于等于2的子数组求和为k的整数倍。并返回有没有这样的子数组。
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.
思路：
这几天做的都是动态规划，今天这个题我想到的思路的时间复杂度最小也是数组长度的平方（不过打败了百分之七十多的提交者）。既然要用动态规划，先看一下哪些地方会有重复运算现象进而可以改进。很明显，一个比较长的子数组的和可以由比它长度小一的子数组的和加上一个元素得到。
这样，我们就有了初步思路，长度为1的数组有n个，长度为2的数组有n-1个...这样可以用一个二维数组存储这些求和，在求长度为x的数组的和的时候，可以用到长度为x-1的数组的和，再加上一个数就能求出结果。
但是，空间能不能再小一些呢，像我之前写过的最大股票利润里面也有一个类似的例子。就是用长度为x的数组的和的数据时，前面的数据已经不需要了。所以我门可以只用一个一维数组，每次更新，前面不用的数据直接被取代就行了。
最后，除了核心的思路：
k可以是0啊！！！！
你考虑了？k是0直接返回不能？数组元素可以都是0啊！！！
什么？你还考虑了？数组元素可以只有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;
}