最大サイズのサブアレイの合計は、C++ではkに等しい

numsという配列とターゲット値kがあるとすると、合計がkになるサブ配列の最大長を見つける必要があります。存在しない場合は、代わりに0を返します。

したがって、入力がnums =[1、-1、5、-2、3]、k =3のようである場合、サブ配列[1、-1、5、-2]の合計は4になるため、出力は4になります。 3で、最長です。

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

• ret：=0

• 1つのマップを定義するm

• n：=numsのサイズ

• temp：=0、m [0]：=-1

• 初期化i：=0の場合、i

  • temp：=temp + nums [i]

  • （temp --k）がmの場合、-

    • ret：=retとiの最大値--m[temp --k]

  • 温度がmでない場合、-

    • m [temp]：=i

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxSubArrayLen(vector<int<& nums, int k) {
      int ret = 0;
      unordered_map <int, int> m;
      int n = nums.size();
      int temp = 0;
      m[0] = -1;
      for(int i = 0; i < n; i++){
         temp += nums[i];
         if(m.count(temp - k)){
            ret = max(ret, i - m[temp - k]);
         }
         if(!m.count(temp)){
            m[temp] = i;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int< v = {1,-1,5,-2,3};
   cout << (ob.maxSubArrayLen(v, 3));
}

入力

[1,-1,5,-2,3], 3

出力

4