Giả sử chúng ta có một mảng A gồm các số nguyên. Chúng ta phải tìm số mảng con không rỗng liền nhau có tổng chia hết cho k. Nếu A =[4,5,0, -2, -3,1] và k =5, thì đầu ra sẽ là 7. Có bảy mảng con. [[4,5,0, -2, -3,1], [5], [5,0], [5,0, -2, -3], [0], [0, -2, - 3], [-2, -3]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạo một bản đồ m và đặt m [0] là 1
- temp:=0, ans:=0 và n:=kích thước của mảng a
- cho tôi trong phạm vi từ 0 đến n - 1
- temp:=temp + a [i]
- x:=(temp mod k + k) mod k
- ans:=ans + m [x]
- tăng m [x] lên 1
- trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraysDivByK(vector<int>& a, int k) {
unordered_map <int, int> m;
m[0] = 1;
int temp = 0;
int ans = 0;
int n = a.size();
for(int i = 0; i < n; i++){
temp += a[i];
int x = (temp % k + k) % k;
ans += m[x];
m[x]++;
}
return ans;
}
};
main(){
vector<int> v = {4,5,0,-2,-3,1};
Solution ob;
cout <<(ob.subarraysDivByK(v, 5));
} Đầu vào
[4,5,0,-2,-3,1] 5
Đầu ra
7