在C ++中子数组求和可被K整除

假设我们有一个整数数组A。我们必须找到连续的非空子数组的数量，这些子数组的和可被k整除。如果A = [4,5,0，-2，-3,1]且k = 5，则输出将为7。存在七个子数组。[[4,5,0，-2，-3,1]，[5]，[5,0]，[5,0，-2，-3]，[0]，[0，-2，- 3]，[-2，-3]

为了解决这个问题，我们将遵循以下步骤-

• 制作一张映射m并将m [0]设置为1

• temp：= 0，ans：= 0，n：=数组a的大小

• 对于i，范围为0至n – 1

• temp：= temp + a [i]

• x：=（温度mod k + k）mod k

• ans：= ans + m [x]

• 将m [x]增加1

• 返回ans

让我们看下面的实现以更好地理解-

示例

#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));
}

输入项

[4,5,0,-2,-3,1]
5

输出结果

7