Skip to content

0548._Split_Array_with_Equal_Sum.md

Latest commit

 

History

History
154 lines (96 loc) · 3.86 KB

0548._Split_Array_with_Equal_Sum.md

File metadata and controls

154 lines (96 loc) · 3.86 KB

548. Split Array with Equal Sum

难度: Medium

刷题内容

原题连接

内容描述

Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:

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

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

一遍bug free AC，小自豪

首先数组长度小于7肯定不可以

然后对于j的位置先来一遍for循环，j只要固定了，我们看看前面一半和后面一半能不能分别分开成相等的部分， 然后把这些分成功的部分存下来，前后一比较，如果可以达到4个部分的sum都相等就返回True，时间优化就是使用一个前缀和数组来帮助一下

beats 8.82%

class Solution(object):
    def splitArray(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 7:
            return False
        pref = [nums[0]] * len(nums)
        for idx in range(1, len(nums)):
            pref[idx] = pref[idx-1] + nums[idx]
        for j in range(3, len(nums)-3):
            way1s = self.canSplit(nums[:j], pref[:j]) 
            way2s = self.canSplit(nums[j+1:], [i-pref[j] for i in pref[j+1:]])
            for way1 in way1s:
                for way2 in way2s:
                    if way1[1] == way2[1]:
                        return True
        return False        
            
    def canSplit(self, nums, pref):
        res = []
        for idx, num in enumerate(nums):
            if pref[idx-1] == pref[-1] - num - pref[idx-1]:
                res.append((True, pref[idx-1]))
        return res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

在上面思路1的基础上我们可以换种思路，我们可以先确定i的位置，继而k的位置也就确定了，然后我们只需要找j的位置使得 Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) be equal

也就是我们要满足pref[j-1]=pref[i]+sub_sum, pref[j]=pref[k-1]-sub_sum

那么我们可以用字典将prefix sum出现的index存起来，这样可以减少查找时间

beats 98.53%

class Solution(object):
    def splitArray(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 7:
            return False
        pref = [nums[0]] * len(nums)
        lookup = collections.defaultdict(set)
        lookup[pref[0]].add(0)
        for idx in range(1, len(nums)):
            pref[idx] = pref[idx-1] + nums[idx]
            lookup[pref[idx]].add(idx)
        
        for i in range(1, len(nums)-5):
            sub_sum = pref[i-1]
            if pref[-1] - sub_sum in lookup:
                for k in lookup[pref[-1]-sub_sum]:
                    if i + 4 <= k <= len(nums) - 2:
                        t1 = pref[i] + sub_sum
                        t2 = pref[k-1] - sub_sum
                        print(t1, t2)
                        if t1 in lookup and t2 in lookup:
                            for xj in lookup[t1]:
                                for yj in lookup[t2]:
                                    if xj == yj - 1:
                                        return True
        return False