## 题目描述：

LeetCode 548. Split Array with Equal Sum

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

## 题目大意：

1. 0 < i, i + 1 < j, j + 1 < k < n - 1
2. 子数组和 (0, i - 1), (i + 1, j - 1), (j + 1, k - 1)  以及 (k + 1, n - 1) 相等

1. 1 <= n <= 2000.
2. 给定数组元素范围 [-1,000,000, 1,000,000].

## 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
``````

Pingbacks已关闭。