Shortest subarray with sum at least k

Правка en1, от aakarshmadhavan, 2018-07-10 06:45:59
Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

EXAMPLE:
Input: A = [2,-1,2], K = 3
Output: 3
---------
Input: A = [1,2], K = 4
Output: -1
---------
Input: A = [84,-37,32,40,95], K = 167
Output: 3

I have tried 2-pointers/sliding-window but it can't handle negative cases and gives the wrong answer. Can the geniuses of CF help me out on how to approach this problem?

Here is my (non working) code:

public int shortestSubarray(int[] A, int K) {
        int ptr = 0;
        int sum = 0;
        int sol = Integer.MAX_VALUE;
        for(int i = 0; i < A.length; ++i){
            sum += A[i];
            while(sum >= K){
                sol = Math.min(sol, i - ptr + 1);
                sum -= A[ptr++];
            }
            
        }
        return (sol == Integer.MAX_VALUE) ? -1 : sol;
    }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский aakarshmadhavan 2018-07-10 06:45:59 1015 Initial revision (published)