C++でKで割り切れるサブアレイの合計

整数の配列Aがあるとします。合計がkで割り切れる、連続する空でないサブアレイの数を見つける必要があります。 A =[4,5,0、-2、-3,1]およびk =5の場合、出力は7になります。7つのサブ配列があります。 [[4,5,0、-2、-3,1]、[5]、[5,0]、[5,0、-2、-3]、[0]、[0、-2、- 3]、[-2、-3]]

これを解決するには、次の手順に従います-

• 1つのマップmを作成し、m[0]を1に設定します
• temp：=0、ans：=0、およびn：=配列のサイズa
• 0からn–1の範囲のiの場合
  • temp：=temp + a [i]
  • x：=（temp mod k + k）mod k
  • ans：=ans + m [x]
  • m[x]を1増やします
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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