[LeetCode 523] Continuous Subarray Sum

作者 Shilei Tian 日期 2017-03-25
[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 nk 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:

  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.

解题思路

这道题目如果很直观地做,很容易就想到暴力的方法,利用二重循环遍历上界和下界,然后再用一个循环将这一段区间内的元素加起来,时间复杂度为 $\mathcal{O}(n^3)$。稍微进行一点优化,利用 $sum(i,j)=sum(j)-sum(i-1)$ 就可以得到一个时间复杂度为 $\mathcal{O}(n^2)$ 的算法,具体的代码如下:

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

这里我们使用 unordered_map 来进行存储是为了得到 sum(-1) 这种情况,否则需要利用 if 来进行判断,可能时间耗费的比较大。运行所有的测试样例需要 343 ms,击败了 2.70% 的人,效果还是比较差的。

那么我们想,有没有 $\mathcal{O}(n)$ 的算法?其实还真有的。和上面一样,我们用 sum(i) 来表示从第 0 个元素到第 i 个元素的和。假如 sum(i) = m,存在某一个 j 使得 sum(j) = n * k + m,这里 n 可以为任意一个自然数,那么是不是就说明,从 ij 之间的和是 n * k,也就满足了题目的要求?那么我们如何来判断呢?如果我们对 sum(i)k 取模,然后将 sum(j) 取模,最后二者得到的数字是一样的!不信?假如我们 sum(m) = 5,设 k = 4,然后这样 sum(i) % k = 1,再设 sum(j) = 13,所以就有 sum(j) % k = 1,是不是一样的?因此,我们只需要存储从 0 开始到 i 所有元素之和对 k 进行去模的结果,然后判断这个结果是否在之前出现过,如果出现过,就说明从之前的那个元素到现在的这个元素之间的和肯定是 k 的某个倍数,这样就可以了。

但是要考虑一个特殊的情况,那就是 k = 0 的时候。如果 k = 0,那么我们直接存 sum 本身就好了。

代码如下:

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;
}
};

由于只是判断是否出现过,unordered_set 即可,不需要 unordered_map。一下子时间复杂度就变成了 $\mathcal{O}(n)$,运行时间变成 43 ms!