Split Array With Equal Sum


  • 0

    Click here to see the full article post


  • 0

    using DFS can also be accepted

    public class Solution {
        public boolean splitArray(int[] nums) {
            int sum = 0, sub = 0;
            for (int num : nums) sum += num;
            //划分i,不能大于nums.length-5,要至少剩下5个留给剩下的三分来分
            for (int i = 1; i + 5 < nums.length; i++) {
                //过滤掉划分值为0的,因为重复了
                if (i != 1 && nums[i - 1] == 0) continue;
                sub += nums[i - 1];
                if (dfs(nums, i + 1, sub, sum - sub - nums[i], 1)) return true;
            }
            return false;
        }
        
        private boolean dfs(int[] nums, int start, int target, int left, int depth) {
            if (depth == 3) {
                if (left == target) return true;
                return false;
            }
            
            int sub = 0;
            for (int j = start + 1; j + 5 - depth * 2 < nums.length; j++) {
                sub += nums[j - 1];
                if (sub == target) {
                    if (dfs(nums, j + 1, target, left - sub - nums[j], depth + 1)) {
                        return true;
                    }
                }
            }
            
            return false;
        }
    }
    

  • 0

    Solution O(N^2)

    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))

  • 0
    T

    To find positions of i,j,k in the array, just need to select i first, record the sum of first i-1 elements as testSum, use the testSum to search for j in the subarray [i:], if any then k in the subarray [j:]. If j, k are found, done. Otherwise select another i until all possible positions for i have been tested.


  • 0

    DFS approach is getting accepted because of some weak test cases.


  • 0
    S

    what's the complexity of the DFS solution?


  • 0
    X

    No, I think time complexity is O(n^2log(n)) , because set.add() will cost log(n)


  • 0

    @xhd2015 For HashSet , all operations is O(1) if proper hash function is applied.


  • 0
    X

    @lee215 yeah,I was wrong


  • 0
    A

    I believe the animation might be wrong? See the screenshot below:
    0_1493002922513_Capture.PNG

    sum[k-1] - sum[j] = 28 - 20 = 8
    sum[n-1] - sum[k] = 36 - 30 = 6

    8 != 6


  • 0

    @aruballos Thanks for pointing it out. I have updated the animation. Please take a look.


  • 0

    You miss the ending ')' in this line: if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))


Log in to reply
 

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