Leetcode 974. Subarray Sums Divisible by K

[Woodyiiiiiii]

这道题有关subarray的，一开始想用滑动窗口来做，但显然是不行的。

那么考虑到利用Divisible by K的性质，那么就可以使用前缀和+map的思想，对每次的和进行对K取余，得到一定范围的数，然后用Map回顾前面遍历的子数组的和，两者之间的差值从而构成新的子数组，最后找到符合条件的个数。

关键是，负数如何处理？不能不处理，因为每次的和都会取余，负数影响下次和。观察得知加上K即可。

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> kMap = new HashMap<>();
        int ans = 0;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            sum %= k;
            if (sum == 0) ++ans;
            if (sum < 0) sum += k;
            if (kMap.containsKey(sum)) {
                ans += kMap.get(sum);
            }
            kMap.put(sum, kMap.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

此外，用数组的话可以比map更快，但显然空间上利用小，而且可能会爆栈，所以用map最好。

所以对于subarray类型的题目，除了滑动窗口外，特殊情况下(比如能整除K)可以使用前缀和或Map。

类似K能整除的类型题目：

• 1590. Make Sum Divisible by P

---

• 974. Subarray Sums Divisible by K