[LeetCode] 523. Continuous Subarray Sum

【原题】 Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23,2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

【解释】 给定一个数组和一个target，要求返回数组中是否存在连续子数组的和是k的倍数，要求连续子数组的元素个数大于2 【思路】

思路一、 直接从每一个元素开始，依次和其后的元素分别相加，如果为k的倍数返回true即可。O(n^2)的解法，这里略过。

思路二、 o(n^2)的方法有点low，想用求最大子数组和的滑动窗口的思想来做，但没有解出来。于是就看了solution。 需要使用一个定理：

如果x和y除以z同余，那么x-y一定可以整除z

public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);//为了处理nums=[0,0] k=-1这样的情况
        int sum = 0;
        for (int i=0;i<nums.length;i++) {
            sum += nums[i];
            if (k != 0) sum %= k; 
            Integer prev = map.get(sum);
            if (prev != null) {
                if (i - prev > 1) return true;//若找到相同的余数，并且元素不少于两个，利用上面的定理，则返回true
            }
            else map.put(sum, i);//否则将余数和index保存至map
        }
        return false;
    }

这种题目之前没有做过确实很难想到这样的解法，具有很强的技巧性。

参考： https://discuss.leetcode.com/topic/80793/java-o-n-time-o-k-space