C++で合計が等しい配列を分割

n個の整数の配列があるとすると、これらの条件に従うトリプレット（i、j、k）があるかどうかを確認する必要があります-

• 0

• サブ配列の合計（0、i-1）、（i + 1、j-1）、（j + 1、k-1）、および（k + 1、n-1）は同じになります。

サブ配列（L、R）は、Lでインデックス付けされた要素からRでインデックス付けされた要素までの元の配列のスライスです。

したがって、入力が[1,2,1,2,1,2,1]の場合、i =1、j =3、k =5のように、出力はTrueになります。

sum(0, i - 1) = 1 sum(0, 0) = 1
sum(i + 1, j - 1) = 1 sum(2, 2) = 1
sum(j + 1, k - 1) = 1 sum(4, 4) = 1
sum(k + 1, n - 1) = 1 sum(6, 6) = 1

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

• n：=numsのサイズ

• サイズnの配列の合計を定義します

• sums [0]：=nums [0]

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

  • sums [i]：=sums [i] +（nums [i] + sums [i-1]）

• 初期化j：=3の場合、j − nの場合、更新（jを1増やします）、実行-

  • 1つのセットを定義する

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

    • sum1：=sums [i-1]

    • sum2：=sums [j --1] --sums [i]

    • sum1がsum2と同じ場合、-

      • sum1をsに挿入します

  • 初期化k：=j + 2の場合、k

    • sum1：=sums [k --1] --sums [j]

    • sum2：=sums [n --1] --sums [k]

    • sum1がsum2と同じで、sum1がsにある場合、-

      • trueを返す

• falseを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool splitArray(vector<int>& nums) {
      int n = nums.size();
      vector<int> sums(n);
      sums[0] = nums[0];
      for (int i = 1; i < n; i++) {
         sums[i] += (nums[i] + sums[i - 1]);
      }
      for (int j = 3; j < n; j++) {
         set<int> s;
         for (int i = 1; i < j - 1; i++) {
            int sum1 = sums[i - 1];
            int sum2 = sums[j - 1] - sums[i];
            if (sum1 == sum2)
               s.insert(sum1);
         }
         for (int k = j + 2; k < n - 1; k++) {
            int sum1 = sums[k - 1] - sums[j];
            int sum2 = sums[n - 1] - sums[k];
            if (sum1 == sum2 && s.count(sum1))
               return true;
            }
         }
         return false;
      }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1,2,1,2,1};
   cout << (ob.splitArray(v));
}

入力

{1,2,1,2,1,2,1}

出力

1