O(n2) solution


  • 1
    X
        public boolean splitArray(int[] nums) {
            int n = nums.length;
            if(n < 7) return false;
            int[] sum = new int[nums.length];
            int res = 0;
            for(int i = 0; i < n; i++){
                res += nums[i];
                sum[i] = res;
            }
            
            for(int j = 3; j < n - 3; j++){
                HashSet<Integer> tmp = new HashSet<>();
                for(int i = 1; i < j - 1; i++){
                    if(sum[i - 1] == sum[j - 1] - sum [i]){
                        tmp.add(sum[i - 1]);
                    }
                }
                for(int k = j + 2; k < n - 1; k++){
                    if(sum[k - 1] - sum[j] == sum[n - 1] - sum[k] && tmp.contains(sum[n - 1] - sum[k])) return true;
                }
            }
            
            return false;
        }
    }
    

    One thing to notice is that there could be multiple possible sum satisfy the first half, so we need to use a set to contain all of them.


Log in to reply
 

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