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]
來源：力扣（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;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/49759.html
標籤：其他
上一篇：重學資料結構之圖