5 lines simple Python


  • 2

    The key idea is kind like divide and conquer (only twice though).

    First, for every middle point j, we split nums into two subarray nums[:j] and nums[j+1:]. In the helper function split, try to remove one element from the subarray, if the the sums of two remaining left and right sub-subarray are equal, we keep the sum of sub-subarray in the set we return. Once we have any intersection between the two sets, we know we can make it.

    Keep in mind len(nums) > 6 is a must since we need to split original array into four parts.

    class Solution(object):
        def splitArray(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            def split(A):
                total = sum(A)
                for i in range(1, len(A)): A[i] += A[i-1]
                return {A[i-1] for i in range(1, len(A)-1) if A[i-1] == total - A[i]}
                
            return len(nums) > 6 and any(split(nums[:j]) & split(nums[j+1:]) \
                                 for j in range(3, len(nums)-3))
    

  • 0

    You don't need the explicit len(nums) > 6 test. If it's false, then the any(...) is false as well.


  • 0

    @StefanPochmann
    Yeah I know, just wanna save some efforts for the impossible cases. Thanks for point that out anyway, :)


  • 0

    You don't need to calculate A every time. Here is my version:

    def splitArray(self, nums):
            n = len(nums)
            s = [0] * (n + 1)
            for i in range(n): s[i + 1] = s[i] + nums[i]
            def check(l, r):
                return set(s[m] - s[l] for m in range(l + 1, r + 1) if s[m] - s[l] == s[r + 1] - s[m + 1])
            return any(check(0, j - 1) & check(j + 1, n - 1) for j in range(n))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.