Split Array With Equal Sum


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.length5,要至少剩下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; } }

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

To find positions of i,j,k in the array, just need to select i first, record the sum of first i1 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.



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