Java O(n^2) solutions


  • 0
    V
    
    public class Solution {
        public boolean splitArray(int[] nums) {
            if (nums.length < 4) return false;
            
            int n = nums.length;
            int[] sums = new int[n];
            sums[0] = nums[0];
            for (int i = 1; i < n; i++) {
                sums[i] = sums[i - 1] + nums[i];
            }
            
            for (int j = 2; j < n - 4; j++) {
                Set<Integer> s = new HashSet<>();
                for (int partition = 1; partition <= j - 1; partition++) {
                    if (sums[partition - 1] == sums[j] - sums[partition]) {
                        s.add(sums[partition - 1]);
                    }
                }
                
                if (!s.isEmpty()) {
                    for (int partition = j + 3; partition < n - 1; partition++) {
                        int sum = sums[partition - 1] - sums[j + 1];
                        if (s.contains(sum) && sum == sums[n - 1] - sums[partition]) return true;
                    }
                }
            }
            
            return false;
            
        }
    }
    

Log in to reply
 

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