# [LeetCode] 548. Split Array with Equal Sum 分割数组成和相同的子数组

2021年09月15日 阅读数：1

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

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.java

Example:python

```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. 1 <= n <= 2000.
2. Elements in the given array will be in range [-1,000,000, 1,000,000].

Java: 暴力， TLEhtm

```public class Solution {

public int sum(int[] nums, int l, int r) {
int summ = 0;
for (int i = l; i < r; i++)
summ += nums[i];
return summ;
}

public boolean splitArray(int[] nums) {
if (nums.length < 7)
return false;
for (int i = 1; i < nums.length - 5; i++) {
int sum1 = sum(nums, 0, i);
for (int j = i + 2; j < nums.length - 3; j++) {
int sum2 = sum(nums, i + 1, j);
for (int k = j + 2; k < nums.length - 1; k++) {
int sum3 = sum(nums, j + 1, k);
int sum4 = sum(nums, k + 1, nums.length);
if (sum1 == sum2 && sum3 == sum4 && sum2 == sum4)
return true;
}
}
}
return false;
}
}　　```

Java: 暴力，TLE

```public class Solution {
public boolean splitArray(int[] nums) {
if (nums.length < 7)
return false;
int[] sum = new int[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
for (int i = 1; i < nums.length - 5; i++) {
int sum1 = sum[i - 1];
for (int j = i + 2; j < nums.length - 3; j++) {
int sum2 = sum[j - 1] - sum[i];
for (int k = j + 2; k < nums.length - 1; k++) {
int sum3 = sum[k - 1] - sum[j];
int sum4 = sum[nums.length - 1] - sum[k];
if (sum1 == sum2 && sum3 == sum4 && sum2 == sum4)
return true;
}
}
}
return false;
}
}
```

Java: TLE

```public class Solution {
public boolean splitArray(int[] nums) {
if (nums.length < 7)
return false;

int[] sum = new int[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
for (int i = 1; i < nums.length - 5; i++) {
int sum1 = sum[i - 1];
for (int j = i + 2; j < nums.length - 3; j++) {
int sum2 = sum[j - 1] - sum[i];
if (sum1 != sum2)
continue;
for (int k = j + 2; k < nums.length - 1; k++) {
int sum3 = sum[k - 1] - sum[j];
int sum4 = sum[nums.length - 1] - sum[k];
if (sum3 == sum4 && sum2 == sum4)
return true;
}
}
}
return false;
}
}　　```

Java: Accepted

```public class Solution {
public boolean splitArray(int[] nums) {
if (nums.length < 7)
return false;
int[] sum = new int[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
for (int j = 3; j < nums.length - 3; j++) {
HashSet < Integer > set = new HashSet < > ();
for (int i = 1; i < j - 1; i++) {
if (sum[i - 1] == sum[j - 1] - sum[i])
}
for (int k = j + 2; k < nums.length - 1; k++) {
if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))
return true;
}
}
return false;
}
}　　```

Python:

```# Time:  O(n^2)
# Space: O(n)

class Solution(object):
def splitArray(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) < 7:
return False

accumulated_sum = [0] * len(nums)
accumulated_sum[0] = nums[0]
for i in xrange(1, len(nums)):
accumulated_sum[i] = accumulated_sum[i-1] + nums[i]
for j in xrange(3, len(nums)-3):
lookup = set()
for i in xrange(1, j-1):
if accumulated_sum[i-1] == accumulated_sum[j-1] - accumulated_sum[i]:
for k in xrange(j+2, len(nums)-1):
if accumulated_sum[-1] - accumulated_sum[k] == accumulated_sum[k-1] - accumulated_sum[j] and \
accumulated_sum[k - 1] - accumulated_sum[j] in lookup:
return True
return False　　```

Python:

```class Solution(object):
def splitArray(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
size = len(nums)
sums = [0] * (size + 1)
for x in range(size):
sums[x + 1] += sums[x] + nums[x]

idxs = collections.defaultdict(list)
for x in range(size):
idxs[sums[x + 1]].append(x)

jlist = collections.defaultdict(list)
for i in range(1, size):
for j in idxs[2 * sums[i] + nums[i]]:
if i < j < size:
jlist[sums[i]].append(j + 1)

for k in range(size - 2, 0, -1):
for j in jlist[sums[size] - sums[k + 1]]:
if j + 1 > k: continue
if sums[k] - sums[j + 1] == sums[size] - sums[k + 1]:
return True
return False　　```

C++:

```class Solution {
public:
bool splitArray(vector<int>& nums) {
if (nums.size() < 7) return false;
int n = nums.size();
vector<int> sums = nums;
for (int i = 1; i < n; ++i) {
sums[i] = sums[i - 1] + nums[i];
}
for (int j = 3; j < n - 3; ++j) {
unordered_set<int> s;
for (int i = 1; i < j - 1; ++i) {
if (sums[i - 1] == (sums[j - 1] - sums[i])) {
s.insert(sums[i - 1]);
}
}
for (int k = j + 1; k < n - 1; ++k) {
int s3 = sums[k - 1] - sums[j], s4 = sums[n - 1] - sums[k];
if (s3 == s4 && s.count(s3)) return true;
}
}
return false;
}
};
```

C++:

```class Solution {
public:
bool splitArray(vector<int>& nums) {
if (nums.size() < 7) return false;
int n = nums.size(), target = 0;
int sum = accumulate(nums.begin(), nums.end(), 0);
for (int i = 1; i < n - 5; ++i) {
if (i != 1 && nums[i] == 0 && nums[i - 1] == 0) continue;
target += nums[i - 1];
if (helper(nums, target, sum - target - nums[i], i + 1, 1)) {
return true;
}
}
return false;
}
bool helper(vector<int>& nums, int target, int sum, int start, int cnt) {
if (cnt == 3) return sum == target;
int curSum = 0, n = nums.size();
for (int i = start + 1; i < n + 2 * cnt - 5; ++i) {
curSum += nums[i - 1];
if (curSum == target && helper(nums, target, sum - curSum - nums[i], i + 1, cnt + 1)) {
return true;
}
}
return false;
}
```

C++: 暴力+优化

```class Solution {
public:
bool splitArray(vector<int>& nums) {
int n = nums.size();
vector<int> sums = nums;
for (int i = 1; i < n; ++i) {
sums[i] = sums[i - 1] + nums[i];
}
for (int i = 1; i <= n - 5; ++i) {
if (i != 1 && nums[i] == 0 && nums[i - 1] == 0) continue;
for (int j = i + 2; j <= n - 3; ++j) {
if (sums[i - 1] != (sums[j - 1] - sums[i])) continue;
for (int k = j + 2; k <= n - 1; ++k) {
int sum3 = sums[k - 1] - sums[j];
int sum4 = sums[n - 1] - sums[k];
if (sum3 == sum4 && sum3 == sums[i - 1]) {
return true;
}
}
}
}
return false;
}
};
```

Split an array into two equal Sum subarrays