[数据结构与算法]leetcode 523. 连续的子数组和 -前缀和

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

题目

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

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

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

前缀和

普通前缀和中，求得子序列的和是定值，这里是k倍，可以通过遍历其倍数解决该条件。

该题的数据有些特殊，全部为正数，并且只需要判断是否存在，不需要记录个数。hashmap中的Value不需要记录出现的次数例。但考虑到本体对数组长度有要求，value可以记录index，用于计算长度。

下面的代码确实可以通过，甚至是比官方的快一些，但比较宁巴。

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        
        HashMap<Integer,Integer> map = new HashMap();
        int len = nums.length;
        if(len <2)
            return false;
        map.put(0,-1);// 当不存在前缀时，对应的值，这里的index时自序列的前一位，故为-1

        int cur = nums[0];
        map.put(cur,0);

        //int count = 0;

        for(int i=1;i<len;i++){
            cur += nums[i];
            if(nums[i] == 0 && nums[i-1]==0 ){ // n=0
                return true;
            }

            int n =k;
            while(n<=cur){
            if( map.containsKey(cur - n ) && (i - map.get(cur-n))>1 ){
                    return true;
                }
                n += k;
            }
            if(nums[i]!= 0)
            map.put(cur,i);
        }
        return false;

    }
}
执行用时: 12 ms
内存消耗: 52.6 MB

同余

官方给出的，确实思路上更整齐。n倍中，n是不确定的，通过取余将n处理掉。

b%k = a%k 等价于 (b-a)%k= n

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int len = nums.length;
        if(len <2)
           return false;

        HashMap<Integer,Integer> map = new HashMap();
        map.put(0,-1);// from root
        int cur =0;
        int mod;
        for(int i=0;i<len;i++){
            cur += nums[i];
            mod = cur %k ;
            if(map.containsKey( mod)){
                if(  (i-map.get(mod)>1))
                return true;
            }else{
                 map.put(mod,i);
            } 
        }
        return false;
    }
}