# Lazy java 27ms O(n^2) solution explained.

• The point in this algorithm is to do as less work as possible. And if we already found the answer, the program should stop immediately.
In the first round, I compute all possible sum for the 4th subarray.
In the second round, I check if there is a possibility that the sum of 1st subarray is the same as the 4th subarray.
In the last round, I check if I can found a valid j value and stop when I found it.
The best case: O(N); the worst case: O(N^2).
Welcome to any optimization!

``````public static boolean splitArray(int[] nums) {
if(nums.length < 7) return false;
int sum = nums[nums.length - 1];
HashMap<Integer, LinkedList<Integer>> map = new HashMap();
for(int i = nums.length - 2; i > 0; i--) {
else {
map.put(sum, tmp);
}
sum += nums[i];
}
sum = nums[0];
for(int i = 1; i < nums.length - 5; i++) {
if(map.containsKey(sum)) {
for(Integer k : list) {
if(k > i + 3 && checker(sum, nums, i + 1, k - 1)) return true;
}
}
sum += nums[i];
}
return false;
}

private static boolean checker(int target, int[] array, int start, int end) {
int sum = 0;
for(int i = start; i <= end; i++) sum += array[i];
int left = array[start], right = sum - array[start] - array[start + 1];
for(int i = start + 1; i < end; i++) {
if(left == right && left == target) return true;
else {
left += array[i];
right -= array[i + 1];
}
}
return false;
}
``````

• @qswawrq Nice solution to calculate 4th array first to handle the test case
[0 0 0 0 0 ... 1 1 1 1 1 1 1 1 ]! However, I think your solution is still O(n^3) in the worst case. For example,
[0 0 0 0 0 0 ... 01 1 1 1 1 1 1 1 1..1 0 0 0 ... 0], which has n/3 0s, n/3 1s, and n/3 0s.
The function checker() is O(n); for i = 1 to n/3, list = map.get(0) size is n/3, so the total time is O(n^3).

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