548.Split Array with Equal Sum
Problem description:
Given an integer array nums
of length n
, return true
if there is a triplet (i, j, k)
which satisfies the following conditions:
0 < i, i + 1 < j, j + 1 < k < n - 1
- The sum of subarrays
(0, i - 1)
,(i + 1, j - 1)
,(j + 1, k - 1)
and(k + 1, n - 1)
is equal.
A subarray (l,r)
represents a slice of the original array starting from the element indexed l
to the element indexed r
.
Example 1:
1 | Input: nums = [1,2,1,2,1,2,1] |
Example 2:
1 | Input: nums = [1,2,1,2,1,2,1,2] |
Constraints:
n == nums.length
1 <= n <= 2000
106 <= nums[i] <= 106
Solution:
The idea is we deal with left side first. We store every equaled sum in a hashSet. Then check right side, if could find equaled sum on right side that occurred on left side, then return True.
Observation on the array
1 | minimum length of array is 7 |
- Compute prefix sum
prefix
. This could optimize during calculate the partial sum - For every
j
, firstly, we find all the left cut’s positions,i
, that lead to equalizing the sum of the first and the second part (i.e.sum[i-1] = sum [j-1] - sum[i]
) - For right cut, try to find (
sum[n-1]-sum[k]=sum[k-1] - sum[j]
)
1 | class Solution: |
time: O(n^2)
time complexity: $O()$
space complexity: $O()$
reference:
related problem: