sottoarray minima che è più grande di una chiave

Question

Ho un array di interi (non necessariamente ordinate), e voglio trovare un sottoarray contiguo, che somma dei suoi valori sono minimi, ma più grande di un valore specifico K

per esempio :

ingresso: array: {1,2,4,9,5}, valore chiave: 10

uscita: {4,9}

So che è facile da fare questo in O(n^2) ma voglio fare questo in O(n)

mia idea: Non sono riuscito a trovare lo stesso in O(n) ma tutto quello che potevo pensare era della complessità temporale O(n^2).

Answer 1

Supponiamo che possa avere solo valori positivi.

Quindi è facile.

La soluzione è uno dei subarray contigui minimi (più corti) la cui somma è > K.

Prendere due indici, uno per l'inizio del subarray e uno per la fine (uno dopo la fine), iniziare con end = 0 e start = 0. Inizializzare sum = 0; e min = infinity

while(end < arrayLength) { 
    while(end < arrayLength && sum <= K) { 
     sum += array[end]; 
     ++end; 
    } 
    // Now you have a contiguous subarray with sum > K, or end is past the end of the array 
    while(sum - array[start] > K) { 
     sum -= array[start]; 
     ++start; 
    } 
    // Now, you have a _minimal_ contiguous subarray with sum > K (or end is past the end) 
    if (sum > K && sum < min) { 
     min = sum; 
     // store start and end if desired 
    } 
    // remove first element of the subarray, so that the next round begins with 
    // an array whose sum is <= K, for the end index to be increased 
    sum -= array[start]; 
    ++start; 
} 

Poiché entrambi gli indici solo vengono incrementati, l'algoritmo è O(n).

Answer 2

Implementazione Java per numeri positivi e negativi (non completamente sicuri sui numeri negativi) che funzionano in tempo O (n) con O (1) spazio.

public static int findSubSequenceWithMinimumSumGreaterThanGivenValue(int[] array, int n) { 

    if (null == array) { 
     return -1; 
    } 

    int minSum = 0; 
    int currentSum = 0; 
    boolean isSumFound = false; 
    int startIndex = 0; 
    for (int i = 0; i < array.length; i++) { 
     if (!isSumFound) { 
      currentSum += array[i]; 
      if (currentSum >= n) { 
       while (currentSum - array[startIndex] >= n) { 
        currentSum -= array[startIndex]; 
        startIndex++; 
       } 
       isSumFound = true; 
       minSum = currentSum; 
      } 
     } else { 
      currentSum += array[i]; 
      int tempSum = currentSum; 
      if (tempSum >= n) { 
       while (tempSum - array[startIndex] >= n) { 
        tempSum -= array[startIndex]; 
        startIndex++; 
       } 
       if (tempSum < currentSum) { 
        if (minSum > tempSum) { 
         minSum = tempSum; 
        } 
        currentSum = tempSum; 
       } 
      } else { 
       continue; 
      } 
     } 
    } 
    System.out.println("startIndex:" + startIndex); 
    return minSum; 
}