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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个整数数组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

以上是 在C ++中子数组求和可被K整除 的全部内容， 来源链接： utcz.com/z/358551.html

回到顶部