leetcode548 -- Split Array With Equal Sum (Locked)

# 小郑之家~

### 题目

题目的意思是给定一个数组， 就假设数组比较长，问是否存在(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]段的和相等，选出来的三个柱子并没有算在内。



### 解答


class Solution {
public:
bool splitArray(vector<int>& nums) {
int n = nums.size();
if (n < 7) {
return false;
}
vector<int> sums(n, 0);
sums[0] = nums[0];
for (int i = 1; i < n; ++i) {
sums[i] = sums[i - 1] + nums[i];
}
for (int i = 1; i < n - 1; ++i) {
for (int j = i + 2; j < n - 1; ++j) {
for (int k = j + 2; k < n - 1; ++k) {
int part1 = sums[i - 1];                        // [0, i - 1]
int part2 = sums[j - 1] - sums[i];              // [i + 1, j - 1]
int part3 = sums[k - 1] - sums[j];              // [j + 1, k - 1]
int part4 = sums[nums.size() - 1] - sums[k];    // [k + 1, n - 1]
if (part1 == part2 && part2 == part3 && part3 == part4) {
return true;
}
}
}
}
return false;
}
};



class Solution {
public:
bool splitArray(vector<int>& nums) {
int n = nums.size();
if (n < 7) {
return false;
}
vector<int> sums(n, 0);
sums[0] = nums[0];
for (int i = 1; i < n; ++i) {
sums[i] = sums[i - 1] + nums[i];
}
for (int j = 3; j < n - 3; ++j) {         // j is the middle cut
unordered_set<int> hash;
for (int i = 1; i < j - 1; ++i) {
if (sums[i - 1] == sums[j - 1] - sums[i]) {     // compare [0, i - 1] and [i + 1, j - 1]
hash.insert(sums[i - 1]);
}
}
for (int k = j + 2; k < n - 1; ++k) {
if (sums[n - 1] - sums[k] == sums[k - 1] - sums[j] && hash.count(sums[k - 1] - sums[j])) {    //这时候要看当前的这一段的，还要看之前有没有这样的和，有的话，才算是对的.
return true;
}
}
}
return false;
}
};