Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:
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.
Example 2:
Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
Note:
Approach #1: Brute force. [C++]
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
if (nums.size() < 2) return false;
int l = nums.size();
if (k == 0) {
for (int i = 0; i < l-1; ++i)
if (nums[i] + nums[i+1] == 0) return true;
return false;
}
vector<int> sum(l+1, 0);
for (int i = 0; i < l; ++i)
sum[i+1] = sum[i] + nums[i];
for (int i = 0; i < l-1; ++i) {
for (int j = i+2; j <= l; ++j) {
if ((sum[j] - sum[i]) % k == 0) return true;
}
}
return false;
}
};
sum[i] : the sum of nums from 0 to i;
Approach #2: Set. [C++]
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int n = nums.size(), sum = 0, pre = 0;
unordered_set<int> modk;
for (int i = 0; i < n; ++i) {
sum += nums[i];
int mod = k == 0 ? sum : sum % k;
if (modk.count(mod)) return true;
modk.insert(pre);
pre = mod;
}
return false;
}
};
原文：https://www.cnblogs.com/ruruozhenhao/p/10492285.html