原题地址
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;
}
};
