本文共 2533 字，大约阅读时间需要 8 分钟。

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($n^2$)，空间复杂度是O(1)。

当然这道题可以用动态规划的思路去做，但是实现的时会发现时间复杂度接近O($n^2$)，而空间复杂度比暴力破解更糟糕，会是O($n$)，所以就不贴出来我自己实现的动态规划的代码，如果有更好的动态规划的实现方式欢迎评论告知。

参考思路：

在讨论里有个大神给出了时间复杂度是O(

n

$n$)的解法，他的思路非常巧妙，用了数学上的知识，下面给出他的解法的原理： 假设:

$$a[i] + a[i + 1] + ... + a[j] = n_1k + q;$$ 如果存在一个n $$n > j 且a[i] + a[i + 1] + ... + a[j] + ... + a[n] = n_2k + q;$$ 那么 $$a[j + 1] + ... + a[n] = (n_2 - n_1)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
   
    & 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
   
    & nums, int k) {        map
    
      m;        map
     
      ::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 的情况就行。

很多简单的数学性质都是一种很好的算法，所以以后做题时真的除了考虑数据结构外，还得多想想涉及到数学性质，说不定会有更好的解法。这周会再做几道分治相关的题目，坚持刷题，加油~