C++의 연속 부분 배열 합계

음수가 아닌 숫자 목록과 대상 정수 k가 있다고 가정하고 배열에 k의 배수, 합계가 n*인 크기가 최소 2인 연속 하위 배열이 있는지 확인하는 함수를 작성해야 합니다. k 여기서 n은 정수이기도 합니다. 따라서 입력이 [23,2,4,6,7]이고 k =6인 경우 결과는 True가 됩니다. [2,4]는 크기가 2이고 합계가 6이 되기 때문입니다.

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

• m 맵을 만들고 m[0] :=-1 및 sum :=0, n :=nums 배열의 크기로 설정
• 0 ~ n – 1 범위의 i에 대해
  • 합계 :=합 + 숫자[i]
  • k가 0이 아니면 sum :=sum mod k
  • m에 합계가 있고 i – m[sum]>=2이면 true를 반환합니다.
  • m에 합계가 없으면 m[sum] :=i로 설정합니다.
• 거짓 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool checkSubarraySum(vector<int>& nums, int k) {
      unordered_map<int, int> m;
      m[0] = -1;
      int sum = 0;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         sum += nums[i];
         if(k)
         sum %= k;
         if(m.count(sum) && i - m[sum] >= 2){
            return true;
         }
         if(!m.count(sum)) m[sum] = i;
      }
      return false;
   }
};
main(){
   vector<int> v = {23,2,4,6,7};
   Solution ob;
   cout << (ob.checkSubarraySum(v, 6));
}

입력

[23,2,4,6,7]
6

출력

1