523. 连续的子数组和

题目描述

给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。

示例 1：

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

示例 2：

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

解题思路

同前面的整除k连续子数组个数，这里也是用前缀和的方式，不过由于需要连续子数组长度>1，所以hashmap中存的为某个presum的下标。
注意hashmap[0] = -1，方便统一计算i-hashmap[presum]。

bool checkSubarraySum(vector<int>& nums, int k){
    int presum = 0;
    unordered_map<int, int> hash_map;
    hash_map[0] = -1;

    for(int i=0; i<nums.size(); i++){
        presum += nums[i];
        if(k!=0){
            presum = presum % k;
            presum = presum<0 : presum+k:presum;
        }
        if(hash_map.find(presum)){
            if(i-hash_map[presum]>1)
                return true;
        }else{
            hash_map[presum] = i;
        }
    }
    return false;
}