算法15 Continuous Subarray Sum

题目：给定一个非负数列表和一个目标整数 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。
注意：
数组的长度不会超过10,000。
您可以假设所有数字的总和在一个有符号的32位整数的范围内。

思路：根据题意是让我们求出是否存在一个数组其内之和可以整除k。想法一累加求和取出比较。想法二，利用求余函数mod，如果数据sum[i]和sum[j]分别与k的mod值相同，则i到j索引之中就必然有连续数组之和可以整除k。（a +（n * x））％x与（a％x）相同

代码：
先实现特殊想法二

public static boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
    int runningSum = 0;
    for (int i=0;i<nums.length;i++) {
        runningSum += nums[i];
        if (k != 0) runningSum %= k;
        Integer prev = map.get(runningSum);
        if (prev != null) {
            if (i - prev > 1) return true;//这是为了确保子数组的长度至少为2
        }
        else map.put(runningSum, i);
    }
    return false;
}

实现想法一

public static boolean checkSubarraySum(int[] nums, int k) {
    if (nums.length < 2) return false;
    if (checkAllZero(nums)) return true;
    if (k == 0) return checkAllZero(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (j - i > 0 && sum % k == 0) return true;
        }
    }
    return false;
}

private boolean checkAllZero(int[] nums) {
    for (Integer i : nums) {
        if (i != 0) return false;
    }
    return true;
}