974. Subarray Sums Divisible by K. 前缀和、同余定理

佚名 4年前 (2020-05-27) 算法 732人围观抢沙发百度已收录

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

Example 1:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k

1.负数求余
Sum = ((Sum % Mod) + Mod) % Mod;
2.同余定理应用
子数组和能否被K整除转化为
(preSum[j] - preSum[i-1]) mod K == 0
根据同余定理，转化为
preSum[j] mod K == preSum[i-1] mod K

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        map <int,int> Map = {{0 , 1}};  //预置边界情况，第0项为1 
        int ans = 0;
        int preSum = 0;
        for (int elem: A){
            preSum += elem;
            preSum = ((preSum % K) + K) % K;     //负数取模的处理
            ans += Map[preSum];
            Map[preSum]++;
        }

        return ans;
    }
};