连续的子数组和

[louzhedong]

习题

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

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

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

示例 1：

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

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

思路

第一种思路：暴力破解，穷举所有可能，找到第一个满足条件的组合之后就返回结果。肯定会超时

第二种思路：采用前缀和以及Map，我们想象一个场景：数组为[23,2,4,6,7]，k为6，满足条件的字符串为[2,4]。

[23]除以k的余数为5，[23,2,4]的和除以k的余数也是5，说明[2,4]是能除尽k的。所以只要[2,4]的长度大于2，就满足条件。

那如何找到之前数组中跟本次余数一样的数组序列呢？我们可以采用一个Map来保存最早的出现余数时所在的位置

解答

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var checkSubarraySum = function (nums, k) {
    var map = {
        0: -1
    };
    var reminder = 0;
    for (var i = 0, length = nums.length; i < length; i++) {
        reminder = (reminder + nums[i]) % k;
        if (map[reminder] != undefined) {
            var pos = map[reminder];
            if ((i - pos) >= 2) {
                return true
            }
        } else {
            map[reminder] = i;
        }
    }
    return false;
};

go

func checkSubarraySum(nums []int, k int) bool {
    remMap := make(map[int]int)
    remMap[0] = -1

    reminder := 0
    for i := 0; i < len(nums); i++ {
        reminder = (reminder + nums[i]) % k
        value, ok := remMap[reminder]
        if ok {
            if (i - value) >= 2 {
                return true
            }
        } else {
            remMap[reminder] = i
        }
    }
    return false
}