LeetCode 523. Continuous Subarray Sum 解题报告
题目描述
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:
Example 2:
注意事项
1.The length of the array won’t exceed 10,000.
2.You may assume the sum of all the numbers is in the range of a signed 32-bit integer
解题思路
我的思路:
这道题是求给定的一个序列中是否存在一个连续子序列,满足子序列元素之和为k的倍数。最简单的办法,当然是暴力破解,通过二重循环,第一个重循环枚举每一个起点位置,第二重循环遍历以当前起点位置开始,各个长度的连续子序列,一旦找到和为K的倍数就直接返回true,如果一直都没找到就直接返回false,唯一需要注意的地方是几个特殊的测试用例,如nums = [1, 2], k = 0和nums = [0,0], k = 0。所以下面实现代码中的判断的条件才会略显复杂,时间复杂度是O(
n2
),空间复杂度是O(1)。
当然这道题可以用动态规划的思路去做,但是实现的时会发现时间复杂度接近O(
n2
),而空间复杂度比暴力破解更糟糕,会是O(
n
),所以就不贴出来我自己实现的动态规划的代码,如果有更好的动态规划的实现方式欢迎评论告知。
参考思路:
在讨论里有个大神给出了时间复杂度是O(n)的解法,他的思路非常巧妙,用了数学上的知识,下面给出他的解法的原理:
假设:
a[i]+a[i+1]+...+a[j]=n1k+q;
如果存在一个n
n>j且a[i]+a[i+1]+...+a[j]+...+a[n]=n2k+q;
那么
a[j+1]+...+a[n]=(n2−n1)k
因此利用这一结果,可以从序列第一个元素开始遍历,不断累加上当前的元素,并求出当前和除以k后的余数,用一个映射记录该余数出现时的下标,如果同一个余数出现了两次,并且两次出现的下标之差大于1,那么就表示在这两个坐标之间的元素之和是k的倍数,因此就可以返回true,否则最后返回false。
需要注意的两个地方:
1. k可能取0,所以只有当k不为0时才对当前的和求余,同时针对于nums = [0, 0], k = 0的情况,需要添加一个初始映射(0, -1)来确保结果的正确。
2. 下标之差至少为2才算是正确的情况,因为题目要求子序列长度至少为2,以上面的例子就是n至少等于j+2。
具体实现见下面参考代码。
代码
我的代码
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
if (nums.size () < 2)
return false;
int sum = 0;
for (int i = 0; i < nums.size () - 1; i++) {
sum += nums[i];
for (int j = i + 1; j < nums.size (); j++) {
sum += nums[j];
if ((k != 0 && sum % k == 0) ||(k == 0 && sum == 0))
return true;
}
sum = 0;
}
return false;
}
};
参考代码:
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
map<int, int> m;
map<int, int>::iterator itr = m.end();
int sum = 0;
m[0] = -1;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (k)
sum %= k;
itr = m.find(sum);
if (itr != m.end()) {
if (i - itr->second > 1)
return true;
}
else
m[sum] = i;
}
return false;
}
};
总结
这道题是LeetCode Weekly Contest 21的第二道题,子序列和问题有很多变种,和为k倍数问题是其中一种,题目难度不大,可以用各种方式去做,只要注意k取0 的情况就行。
很多简单的数学性质都是一种很好的算法,所以以后做题时真的除了考虑数据结构外,还得多想想涉及到数学性质,说不定会有更好的解法。这周会再做几道分治相关的题目,坚持刷题,加油~