523.连续的子数组和

问题

给定一个包含非负数的数组和一个目标整数 $k$，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 $2$，总和为 $k$ 的倍数，即总和为 $n\ast 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$。

说明:

数组的长度不会超过10,000。 你可以认为所有数字总和在 32 位有符号整数范围内。

解答1

遍历不同长度的子数组，判断是不是能被整除即可。有一个优化点在于可以用动态规划的思路。在len+1长度的子数组遍历时，可以用到len长度的子数组已经计算好的值，不需要再次计算了。

需要clone一份nums数据，空间复杂度是$O(n)$

源码1

java实现

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //新增一个数组保存上一轮的全部sum数据
        //这里容易出错的地方在于将sums的数据初始化为0。会造成基础数据就不对。
        int[] sums = nums.clone();
        //从len=2开始，进行长度不同的遍历
        for(int len=2;len<=nums.length;len++) {
            for(int i = 0; i<=nums.length-len; i++) {
                //此时将sums[i]的数据与nums[i+len-1]的数据相加获得新值
                sums[i] += nums[i+len-1];
                //排除掉[0,0],0 的特殊情况
                if(sums[i] ==0) {
                    return true;
                }
                //判断当前值是不是可以整除，可以直接返回true
                if (k!=0&& sums[i]%k==0) {
                    return true;
                }
            }
        }
        //默认情况
        return false;
    }
}

解答2

引入一个概念，前缀和（prefix sum）。

给定一个数组$x$，数组元素为$x_0,x_1,x_2,...x_{n-1},x_n$ 如果有数组$y$,满足如下条件 $y_0=x_0$ $y_1=x_0+x_1$ $y_2=x_0+x_1+x_2$ $...$ $y_{n-1}=x_0+x_1+x_2+...+x_{n-1}$ $y_n=x_0+x_1+x_2+...+x_{n-1}+x_n$ 那么称$y$为$x$的前缀和数组 例子:

$x$数组	1	2	3	4	5	6
$y$数组	1	3	6	10	15	21

此时可以发现，数组$x$的子序列和均可由前缀和数组$y$获得，如$x_a$至$x_b$子序列的和，可以由$y_b-y_{a-1}$得到。而且也可以用到动态规划的思路，一次遍历生成$y$数组，然后接下来的遍历就可以复用$y$数组了。

源码2

java实现

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //生成前缀和数组，此时已经可以判断一次了
        int[] presums = new int[nums.length];
        for(int i=0;i<nums.length;i++) {
            if (i==0) {
                presums[0]=nums[0];
            } else {
                presums[i] = presums[i-1] + nums[i];
                if (presums[i] == 0) {
                    return true;
                }
                if (k!=0 && presums[i]%k==0) {
                    return true;
                }
            }
        }
        //此时遍历连续子数组的和
        for (int i=1;i<presums.length;i++) {
            for(int len=2;len<=i;len++) {
                //这一步是获取从i-len+1到i的子数组的和
                int sub = presums[i]-presums[i-len];
                if(sub ==0) {
                    return true;
                }
                if (k!=0 && sub%k==0) {
                    return true;
                }
            }
        }
        //默认情况
        return false;
    }
}

代码整体没有难度，需要关注的点在于遍历子数组的和时的边界问题，因为题目要求是最少长度为2，所以len这里需要赋值为2，len<=i的原因在于需要将presums[0]首位数扣除。

解法3

仍然需要解法2的前缀和的概念。 假设有两个索引值$a$与$b,y_a=m\ast k+mo{d}_a,y_b=n\ast k+mo{d}_b$其中$mo{d}_a$与$mo{d}_b$为$y_a$与$y_b$整除k的余数。不难发现这么一个情况，如果$mo{d}_a==mo{d}_b$并且$b-a>1$，那么$a$到$b$的子数组和就是满足要求的数组。 此时可以考虑，将每一个$mod$与其索引值放入一个map中，key为$mod$,value为索引值。每次循环时，判断新值的$mod$是否保存在map中，如果存在，那么判断两个索引值之间的差值是否大于1，大于1就返回true即可 有一种特殊情况，就是$num{s}_0==0$并且$num{s}_i\%k==0$，为了处理这种情况，设置键值对(0,-1) 需要处理连续两个0以及k=0的特殊情况

源码3

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //先处理特殊情况
        //当nums的长度小于2时，必然false
        if (nums.length<2) return false;
        //当相邻两个值均为0时，必然true
        for(int i=0;i<nums.length-1;i++) {
            if(nums[i]==0&&nums[i+1]==0) return true;
        }
        //此时排除掉上一种情况时，如果k==0，那么必然为false
        if (k==0) return false;
        //开始循环
        //构造一个map放入mod与索引
            Map<Integer,Integer> map = new HashMap<>();
        //写入特殊情况的键值对(0,-1)
        map.put(0,-1);
        //构造一个全局变量供每次循环累加使用
        int sum=0;
        for(int i=0;i<nums.length;i++) {
            sum +=nums[i];
            //取余
            int mod = sum%k;
            //判断map中是否已经包含了mod值，
            if (map.containsKey(mod)) {
                //当两个索引值相减大于1时，说明有2个元素及以上的子数组满足条件
                if (i-map.get(i) > 1) {
                    return true;
                }
            } else {
                //将键值对放入map中
                map.put(mod, i);
            }
        }
        //默认情况
        return false;
    }
}

总结

此题目的解法众多，但是快速找到一个时间复杂度与空间复杂度均低的解法还是需要一些思考的。解法1与解法2在leetcode中的耗时大概在66ms左右，解法3耗时在13ms左右。