C++での連続サブアレイ合計

非負の数とターゲット整数kのリストがあるとすると、配列に、合計がkの倍数、合計がn*になる少なくとも2のサイズの連続サブ配列があるかどうかを確認する関数を作成する必要があります。 kここで、nも整数です。したがって、入力が[23,2,4,6,7]のようで、k =6の場合、[2,4]はサイズ2の連続サブ配列であり、合計が6になるため、結果はTrueになります。

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

• マップmを作成し、m [0]：=-1を設定し、sum：=0、n：=nums配列のサイズを設定します
• 0からn–1の範囲のiの場合
  • sum：=sum + nums [i]
  • kがゼロ以外の場合、sum：=sum mod k
  • mに合計があり、i – m [sum]> =2の場合、trueを返します
  • mに合計がない場合は、m [sum]：=iを設定します
• falseを返す

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

例

#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