原题地址

https://leetcode.com/problems/continuous-subarray-sum/description/

题意

判断一个数组中是否有连续的部分（即元素数目大于等于2）的和是给定整数k的倍数

思路

我的就是枚举。。以每个元素开头的所有连续部分都判断一次（判断nums[i]到[i+1],再到[i+2]…… 的和，所以每次在前一次循环的基础上加上当前位置的数）

踩坑

一开始开了多余的数组
忘了考虑k=0的情况
去掉数组后，循环的时候忘记更新变量last的值

代码

最开始的做法

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(k==0) return false;
        int m = nums.size();
        if(m==0) return 0;
        int dp[m][m];
        for(int i =0;i<m;i++){
            for(int j =0;j<m;j++){
                if(i==j) dp[i][j]=nums[i]%k;
                else dp[i][j]=0;
            }
        }
        for(int i =0;i<m;i++){
            for(int j =i+1;j<m;j++){
                dp[i][j]=(dp[i][j-1]+nums[j])%k;
                if(dp[i][j]==0 && j-i>=1) return true;
            }
        }
        return false;
    }
};

因为测试样例里有的nums的长度很大，dp开太大就爆了。看了一下发现dp是多余的，每次循环用一个变量存着就行了

class Solution {
  public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int m = nums.size();
        if (m == 0) return false;
        if (k == 0) {
            for (int i = 0; i < m; i++) {
                int last = nums[i];
                for (int j = i + 1; j < m; j++) {
                    int cur = last + nums[j];
                    last=cur;
                    if (cur == 0 && j - i >= 1) return true;
                }
            }
            return false;
        }
        for (int i = 0; i < m; i++) {
            int last = nums[i] % k;
            for (int j = i + 1; j < m; j++) {
                int cur = (last + nums[j]) % k;
                last = cur;
                if (cur == 0 && j - i >= 1) return true;
            }
        }
        return false;
    }
};