974.Subarray Sums Divisible by K

Tags: Medium Hash Table

Links: https://leetcode.com/problems/subarray-sums-divisible-by-k/

---

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

---

题意是给定一个序列，求其连续子数组使子数组和能够整除K，很显然求连续子数组的和需要利用前缀和的方法。那么接下来就是如何判断子数组和可以整除K了。

假如某一区间段[i,j]的子数组和可以整除K，那么表达式就是： $$ \left(\text{prefixSum}[j] - \text{prefixSum}[i - 1] \right) \% K == 0 \ \text{prefixSum}[j] \% K == \text{prefixSum}[i - 1] \% K $$ 也就意味着假如前缀和下标为j，那么需要计算从0-j-1这些前缀和里面，对K取模和prefixSum[j]相等的个数，既然是取模，那么我们就可以开一个长度为K的数组，并且要保证余数在0-K-1之间，每次只需要把在HashTable里的个数加上即可。

时间复杂度$O(n)$，空间复杂度$O(K)$

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = A.size();
        vector<int> HashTable(K, 0);
        HashTable[0] = 1;
        int cnt = 0; //记录总数
        int sum = 0; //记录前缀和
        for (int i = 0; i < n; ++i) {
            sum = ((sum + A[i]) % K + K) % K; //将余数映射到0-K-1
            if (HashTable[sum] != 0) cnt += HashTable[sum];
            ++HashTable[sum];
        }

        return cnt;
    }
};