# 548. Split Array with Equal Sum 将数组分割成和相等的子数组

@TOC

## # 题目描述

Given an array with n integers, you need to find if there are triplets `(i, j, k)` which satisfies following conditions:

1. `0 < i, i + 1 < j, j + 1 < k < n - 1`
2. Sum of subarrays `(0, i - 1)`, `(i + 1, j - 1)`, `(j + 1, k - 1)` and `(k + 1, n - 1)` should be equal.

where we define that subarray `(L, R)` represents a slice of the original array starting from the element indexed `L` to the element indexed `R`.

Example:

``````Input: [1,2,1,2,1,2,1]
Output: True
Explanation:
i = 1, j = 3, k = 5.
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1
``````

Note:

• `1 <= n <= 2000`.
• Elements in the given array will be in range [-1,000,000, 1,000,000].

## # 解题方法

### # 暴力

C++代码如下：

``````class Solution {
public:
bool splitArray(vector<int>& nums) {
const int N = nums.size();
vector<long long> preSum(N, 0);
long long sum = 0;
for (int i = 0; i < N; ++i) {
sum += nums[i];
preSum[i] = sum;
}
for (int i = 1; i < N; ++i) {
long long sum_0i = preSum[i - 1];
for (int j = i + 1; j < N; ++j) {
long long sum_ij = preSum[j - 1] - preSum[i];
if ((nums[j] == 0 && nums[j - 1] == 0) || sum_0i != sum_ij)
continue;
for (int k = j + 1; k < N; ++k) {
long long sum_jk = preSum[k - 1] - preSum[j];
if (sum_0i != sum_jk)
continue;
long long sum_k = preSum[N - 1] - preSum[k];
if (sum_0i == sum_k) {
return true;
}
}
}
}
return false;
}
};
``````

## # 日期

2019 年 9 月 20 日 —— 是选择中国互联网式加班？还是外企式养生？