在C ++中以相等的总和分割数组

假设我们有一个包含n个整数的数组，我们必须查找是否存在遵循这些条件的三元组(i,j,k)-

• 0 <i，i + 1 <j，j + 1 <k <n-1

• 子数组(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]，则输出将为True，因为i = 1，j = 3，k = 5。

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 <n时，更新（将i增加1），-

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

• 对于初始化j：= 3，当j − n时，更新（将j增加1），执行-

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

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

• 如果sum1与sum2相同，并且sum1在s中，则-

• 返回真

• sum1：= sums [i-1]

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

• 如果sum1与sum2相同，则-

• 将sum1插入s

• 定义一组

• 对于初始化i：= 1，当i <j-1，更新（i增加1）时，执行：-

• 对于初始化k：= j + 2，当k <n-1，更新（将k增加1）时，执行-

• 返回假

例 

让我们看下面的实现以更好地理解-

#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