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]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 지도를 m으로 만들고 m[0]을 1로 설정
temp :=0, ans :=0 및 n :=배열 a의 크기
0 ~ n – 1 범위의 i에 대해
- temp :=temp + a[i]
- x :=(임시 모드 k + k) 모드 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