连续的子数组之和

523 连续的子数组之和

LeetCode

优雅的暴力

如果直接用优雅一点的暴力应该可以跑过
比较每一对子数组判断是否为k的倍数
最坏情况下是k需要最后两个数据相加才使得条件成立，时间复杂度为：O(N^2)

TIPS: 一定要注意细节特殊处理0， 面对0无法进行取余，只有0是0的倍数因此搜索连续两个及以上的0即为true
（这里都是血和泪）
cpp代码如下

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        // 暴力
        if( k == 0){
            if(nums.size() < 2) return false; 
            for(int i=1; i<nums.size(); ++i){
                if(nums[i] == 0 && nums[i-1] == 0) return true;
            }
            return false;
        } // 特别考虑K = 0的情况
        for(int i=0; i<nums.size(); ++i){
            int sum = nums[i];
            for(int j =i+1; j<nums.size(); ++j){
                sum += nums[j];
                if(sum % k == 0) return true;
            }
        }
        return false;
    }
};

hash

参考题560 和为K的连续子数组

思路是一样的不需要求出所有累加和
这里要求的是所有满足是K的倍数的数据
因此可以用到取模
if A MOD B =  C MOD B
then A - C MOD B = 0
由上述关系我们可以知道，我们每求得一个sum就对他取余，然后在到已有的数据中寻找如果有余数和他一样的那他俩的差一定是K的倍数
注意：
题目中还要求至少两个数，因此我们需要存储其索引值，如果相减索引值大于1即为所求（sum的和表示的范围是[0,i]）
初始化的mp[0] = -1; 
为什么要初始化看第560题

c++代码实现如下

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

维护当mp数组中不存在的时候再插入否则会导致输出错误，例如[7,7,7],7
如果直接插入的话会导致输出false.
由于取模值都一样会不断被覆盖

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

但其实在小数据下hash的速度并不会比暴力快多少，由于hash表的访问时间复杂度并不是严格意义上的O(1)还有增大的k系数实际上只快了30ms