Continuous Subarray Sum can be divided by k

这道题要求有没有一个长度超过2子数组的和可以被k整除，因为是被k整除而不是等于k，所以这道题和求和子数组稍微有一点点不一样，但是也不难想到，可以把前缀子数组的累积和取k的膜，这样就只需要找有没有另外一个点的和和当前一样，另外k等于0是一个很麻烦的情况，LeetCode答案给的参考代码用一个0，-1键值对把k等于0和坐标距离的问题都解决了，下面是代码

public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int sum = 0;
        HashMap<Integer, Integer> hashmap = new HashMap<>();

        hashmap.put(0, -1);           // 非常关键的一个键值对，没有的话下面的大于一要改成大于等于且k等于0就需要单独处理了

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (k != 0) {
                sum %= k;
            }
            if (hashmap.containsKey(sum)) {
                if (i - hashmap.get(sum) > 1) {
                    return true;
                }
            } else {
                hashmap.put(sum, i);
            }   
        }

        return false;
    }
}

另外这道题是有O(n^2)的暴力解法的，解法也利用了prefix sum数组，因为不是最优解而且容易想到，这里就不列出来了