目录

• 题目
• 思路
• 答案
• 问题与改进

题目

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/continuous-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

思路

随便写了一下简单的果然超时了。然后就是前缀和加保存余数的办法。

答案

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        //计算前缀和，保存余数，余数一致即可。
        int len = nums.size();
        if(len<2) return false;
        //没有考虑k为0，1的情况
        if(k==0||k==1) return true;
        int sum = 0;
        map<int,int> res;
        //firsttry：没有考虑从首项开始的情况
        res[0] = 1;
        for(int i=0;i<len;i++){
            sum = sum+nums[i];
            if(nums[i]==0 && i+1<len && nums[i+1]==0) return true;
            //thirdtry：没有考虑集中连续几个都是k的情况
            if(nums[i]%k==0 && i+1<len && nums[i+1]%k==0) return true;
            int m = sum%k;
            if(nums[i]%k!=0)
                res[m]++;
            if(res[m]==2) return true;
        }
        return false;
    } 
};

时间复杂度：O(n)
空间复杂度：O(k)

问题与改进

思路很快但是出了很多次错，第一次提交我就忘记了从头开始的子序列和为k倍数的情况，第二次又忘记连续k值的问题，还有什么0的乱七八糟的问题。开始我还用vector存的sum效率太低，但是后面改了依旧很差。我发现我写代码都是先写完再找错，于是后面越改越乱，没有逻辑。

记一下官方解答：

由于哈希表存储的是每个余数第一次出现的下标，因此当遇到重复的余数时，根据当前下标和哈希表中存储的下标计算得到的子数组长度是以当前下标结尾的子数组中满足元素和为 kk 的倍数的子数组长度中的最大值。只要最大长度至少为 22，即存在符合要求的子数组。

一个hash表存的数，我咋就没想到存下标，以至于乱七八糟改了半天。

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int m = nums.size();
        if (m < 2) {
            return false;
        }
        unordered_map<int, int> mp;
        mp[0] = -1;
        int remainder = 0;
        for (int i = 0; i < m; i++) {
            remainder = (remainder + nums[i]) % k;
            if (mp.count(remainder)) {
                int prevIndex = mp[remainder];
                if (i - prevIndex >= 2) {
                    return true;
                }
            } else {
                mp[remainder] = i;
            }
        }
        return false;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/continuous-subarray-sum/solution/lian-xu-de-zi-shu-zu-he-by-leetcode-solu-rdzi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(m)，其中 m 是数组nums 的长度。需要遍历数组一次。

空间复杂度：O(min(m,k))，其中 m 是数组nums 的长度。空间复杂度主要取决于哈希表，哈希表中存储每个余数第一次出现的下标，最多有 min(m,k) 个余数。