70+ms Python solution O(n^2)

  • 0

    Worst case is n^2, but will run much faster in average.

    dict2 stores cumulative sum of input sum[i] as key if there exist two segments separated at m (0 < m < i) are equal, which means nums[0] + ... + nums[m-1] == nums[m+1] + ... + nums[i]. As there are possibly multiple m can satisfy this condition, I use a set to store the sum of each possible segment (nums[0] + ... + nums[m-1]). Similar for dict3, difference is dict3 has keys with 3 segments equal. When sum[i] is in dict3, I check if nums[i+2] + ... + nums[-1] is in dict3[sum[i]].

    class Solution(object):
        def splitArray(self, nums):
            # cumulative sums
            total, sum = 0, []
            for n in nums:
                total += n
            # check if sum[i] satisfy 
            dict2, dict3 = collections.defaultdict(set), collections.defaultdict(set)
            for i in range(1, len(nums)-1):
                if sum[i] in dict3 and sum[len(nums)-1] - sum[i+1] in dict3[sum[i]]:
                    return True
                if sum[i] in dict2:
                    for k in dict2[sum[i]]:
                dict2[sum[i-1]*2 + nums[i]].add(sum[i-1])
            return False

Log in to reply

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