题目分析

这个题目和Leetcode第560题很像，第560题是最基础的前缀和题目，本题进行了扩展，不是求和为k的子数组，而是要求和为k的倍数的子数组，且必须满足子数组的长度至少为2。能否使用类似的方法进行求解呢？

哈希表

本题的题解是第560题的扩展，如果没有做过第560题的小伙伴，建议先去学习该题目。掌握如何在线性的时间复杂度内完成子数组之和的题目。

我们可以通过哈希表查找dic[curSum - k]来判断是否含有值为curSum - k的前缀和，假设第i个前缀和为curSum，第j个前缀和为curSum - k，则从j + 1到i的子数组和为k。这是第560题的主要思路。在本题中k的倍数，无法枚举curSum - k，curSum - 2k等等，要挖掘倍数的特征，如果前i个前缀和模k为p，前j个前缀和模k也为p，则可以得到从j + 1到i的子数组和为k的倍数。此时如果子数组的长度大于等于2，则返回true即可。

算法的**时间复杂度为$O(n)$，因为哈希表只需要保留模k后第一次出现的索引，空间复杂度为$O(k)$**。

下面是Java语言的题解

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur = (cur + nums[i]) % k;
            if (map.containsKey(cur)) {
                if (map.get(cur) + 1 < i) {
                    return true;
                }
            } else {
                map.put(cur, i);
            }
        }
        return false;
    }
}

下面是Kotlin语言的题解

class Solution {
    fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
        val map = mutableMapOf<Int, Int>(0 to -1)
        var cur = 0
        for ((idx, x) in nums.withIndex()) {
            cur = (cur + x) % k
            if (map.containsKey(cur)) {
                if (idx - map[cur]!! > 1) {
                    return true
                }
            } else {
              map[cur] = idx
            }
        }
        return false
    }
}

对比两种语言，可以看出在哈希表的获取和插入时，Java语言必须通过put和get方法进行操作，而Kotlin可以类似于数组一样进行操作，但是**Kotlin语言获取哈希表中的value时，要防止为null，否则无法直接和数值进行计算，因此要使用特殊符号?:0(如果为空则等于0)或者!!(一定不为空)**。

刷题总结

前缀和的题目也已经做过很多次了，多总结，多练习，时间久了就会从量变引起质变。