​LeetCode刷题实战523：连续的子数组和

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 连续的子数组和，我们先来看题面：

https://leetcode-cn.com/problems/continuous-subarray-sum/

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise. An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

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

• 子数组大小 至少为 2 ，且
• 子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

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

示例

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

解题

https://www.cnblogs.com/luo-c/p/13948591.html

思路

使用哈希map来存储累积和除以k后的余数。

为什么存余数？

遍历数组，将当前的累积和存储到map中，如果存在i-j范围内的连续子数组和是k的倍数，那么当前余数sum[j] % k和i-1时刻的余数sum[i-1] % k是一致的。sum[j] = sum[i-1] + n*k，所以map里存余数，如果发现重复余数，则存在连续子数组和是k的倍数。

注意题目中要求子数组长度大于1，map中key是余数，value就存储索引信息，遇到重复余数时，检查一下索引差值是否大于1（对应子数组长度大于1），大于则返回true。

注意一种特殊情况：数组总和刚好能整除k，在索引n-1时在map中首次添加key值：0，当前算法对于这种情况是返回false的，为解决这种冲突，在map中首先添加key值‘0’，索引值置为-1，这样在最后整除时再次添加key值0，发现有重复，判断一下索引差值即可正确判断返回值。

具体代码如下：

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        if(k < 0)
            k = -k;
        if(len < 2)
            return false;
        map<int,int> mp;
        mp[0] = -1; // 处理数组和刚好能整除k的情况
        int rem = 0;
        for(int i = 0;i < len;i++){
            rem += nums[i];
            if(k) // 避免除数为0
                rem = rem % k;
            if(mp.find(rem) != mp.end() ){
                if(i - mp[rem] > 1)
                    return true; 
            }
            else
                mp[rem] = i;
                       
        }
        return false;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-520题汇总，希望对你有点帮助！

LeetCode刷题实战521：最长特殊序列 Ⅰ