原題地址
https://leetcode.com/problems/continuous-subarray-sum/description/
題意
判斷一個數(shù)組中是否有連續(xù)的部分（即元素數(shù)目大于等于2）的和是給定整數(shù)k的倍數(shù)
思路
我的就是枚舉。默责。以每個元素開頭的所有連續(xù)部分都判斷一次（判斷nums[i]到[i+1],再到[i+2]…… 的和，所以每次在前一次循環(huán)的基礎(chǔ)上加上當前位置的數(shù)）
踩坑
- 一開始開了多余的數(shù)組
- 忘了考慮k=0的情況
- 去掉數(shù)組后陶夜，循環(huán)的時候忘記更新變量
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開太大就爆了裆站√醣伲看了一下發(fā)現(xiàn)dp是多余的，每次循環(huán)用一個變量存著就行了
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;
}
};
