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
2
3
4
5
6
7
8
Input: nums = [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

Example 2:

1
2
Input: nums = [1,2,1,2,1,2,1,2]
Output: false

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
2
3
minimum length of array is 7
          i.  j.  k
        0 1 2 3 4 5 6
  1. Compute prefix sum prefix. This could optimize during calculate the partial sum
  2. 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])
  3. For right cut, try to find (sum[n-1]-sum[k]=sum[k-1] - sum[j])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def splitArray(self, nums: List[int]) -> bool:
        if len(nums) < 7: 
            return False
        
        prefix = [0]*len(nums)
        prefix[0] = nums[0]
        for i in range(1, len(nums)):
            prefix[i] = nums[i]+prefix[i-1]
        
        for j in range(3, len(nums)-3):
            visited = set()
            for i in range(1, j-1):
                if prefix[i-1] == prefix[j-1]-prefix[i]:
                    visited.add(prefix[i-1])
            
            for k in range(j+2, len(nums)-1):
                if prefix[k-1]-prefix[j] == prefix[len(nums)-1]-prefix[k] and prefix[len(nums)-1]-prefix[k] in visited:
                    return True
        return False

time: O(n^2)

time complexity: $O()$
space complexity: $O()$
reference:
related problem: