Determine i and k first, then search for j (Accepted easy java solution)


  • 0
    C
    public boolean splitArray(int[] nums) {
        
        if(nums.length < 7) {
            return false;
        } 
        
        // calculate cumulative sum
        int[] sums = new int[nums.length];
        int sum = 0;
        for(int i = 0; i < sums.length; i++) {
            sum += nums[i];
            sums[i] = sum;
        }
        
        // determine i and k first then looking for j
        // to reduce total amount of calculations
        for(int i = 1; i < sums.length - 5; i++) {
            // sum(0, i - 1)
            sum = sums[i] - nums[i];
            for(int k = sums.length - 2; k > 4 && k - i > 3; k--) {
                // sum(k + 1, n - 1)
                if(sum == sums[sums.length - 1] - sums[k]) {
                    for(int j = i + 2; j < k - 1; j++) {
                        // sum(j + 1, k - 1), sum(i + 1, j - 1)
                        if(sum == sums[k] - nums[k] - sums[j] 
                            && sum == sums[j] - nums[j] - sums[i]) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

  • 0

    Your code past simply because test cases are weak. Your solution is O(n^3).

    Try this test case:

    int[] data = new int[2000];
    data[1000] = 1;
    data[1001] = 1;
    // then run your code:
    long start = System.currentTimeMillis();
    splitArray(data);
    System.out.println(System.currentTimeMillis() - start)
    

    I got 3+ seconds on my laptop which I think should get LTE error.


Log in to reply
 

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