C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

サブアレイの合計はC++でKに等しい

整数の配列と整数kがあるとすると、合計がkと同じ連続サブ配列の総数を見つける必要があります。したがって、nums配列が[1、1、1]で、kが2の場合、出力は2になります。

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

  • sums、temp：=0、sums [0]：=1、ans：=0という1つのマップを定義します
  • 0から配列のサイズまでの範囲のiの場合
    • temp：=temp + n [i]
    • 合計にk– tempがある場合、
      • ans：=ans + sums [k --temp]
    • sums[-temp]の値を1増やします
  • 回答を返す
例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int subarraySum(vector<int>& n, int k) {
      unordered_map <int, int> sums;
      int temp = 0;
      sums[0] = 1;
      int ans =0;
      for(int i =0;i<n.size();i++){
         temp+= n[i];
         if(sums.find(k-temp)!=sums.end()){
            ans += sums[k-temp];
         }
         sums[-temp]++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1};
   cout << (ob.subarraySum(v, 2));
}
入力 
[1,1,1]
2

出力

2

  1. C ++のプレフィックス合計を使用したO（n）の最大サブ配列合計

    問題の説明 正の整数と負の整数の配列が与えられた場合、その配列の最大サブ配列の合計を求めます 例 入力配列が− {-12、-5、4、-1、-7、1、8、-3}の場合、出力は9 アルゴリズム 入力配列のプレフィックス合計を計算します。 Initialize− min_prefix_sum =0、res =-infinite i=0からnまでのループを維持します。 （nは入力配列のサイズです。） cand =prefix_sum [i] – mini キャンドの場合 がres（これまでのサブアレイの最大合計）より大きい場合は、resをcandで更新します。

  2. C++で厳密に増加するサブアレイの最大合計を見つける

    n個の整数の配列があるとします。厳密に増加するサブ配列の最大合計を求めます。したがって、配列が[1、2、3、2、5、1、7]のような場合、合計は8になります。この配列には、厳密に増加する3つのサブ配列があります。これらは{1、2、3}、{2 、5}および{1、7}。最大合計サブ配列は{1、7}です。 この問題を解決するには、最大合計と現在の合計を追跡する必要があります。各要素arr[i]について、これがarr [i – 1]より大きい場合は、これを現在の合計に加算します。それ以外の場合、arr[i]は別のサブアレイの開始点です。したがって、現在の合計を配列として更新します。現在の合計を更新す