「Leetcode」974. Subarray Sums Divisible by K（Java）

分析

这题场上前缀和都想出来了，然后就没有然后了。。。哭惹.jpg

前缀和相减能够得到任意一段连续区间的和，然后他们取余\(K\)看余数是否为0就能得到。这是朴素的遍历算法。那么反过来说，如果两个前缀和都对\(K\)余\(p\)，那么他们相减一定能够被K整除。

我们就这么统计就可以了，然后一个简单的求和即可。想到不难，难的是想到。

代码

class Solution {

    public int subarraysDivByK(int[] A, int K) {

        int[] prefix = new int[A.length+1];

        for(int i=0; i<A.length; ++i)

        {

            prefix[i+1] = prefix[i] + A[i];

        }

        int[] cnt = new int[K];

        for(int p: prefix)

        {

            cnt[(p%K+K)%K]++;

        }

        int ans=0;

        for(int c: cnt)

        {

            ans += c*(c-1)/2;

        }

        return ans;

    }

}