在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
热门推荐
10 广西考试祝福语结婚简短
11 猪年祝福语简短小孩
12 元旦祝福语送长辈简短
13 恭喜二宝祝福语简短
14 祝福语暖心话简短
15 国庆中秋祝福语简短兄弟
16 朋友订婚的祝福语简短
17 送弟弟中秋祝福语简短
18 爱生日祝福语简短独特