Minimalna Subarray który jest większy niż Key

Question

Mam tablicę liczb całkowitych (niekoniecznie sortowane) i chcę znaleźć ciągłą subarray których suma jej wartości są minimalne, ale większy od określonej wartości K

na przykład :

wejściowe: tablica: {1,2,4,9,5}, wartość klucza: 10

wyjściowa: {4,9}

Wiem, że łatwo to zrobić w O(n^2) ale chcę to zrobić w O(n)

mój pomysł: I tak nie mogłem znaleźć tego w O(n), ale wszystko, co mogłem pomyśleć, to złożoność czasu.

Answer 1

Załóżmy, że może mieć tylko wartości dodatnie.

To proste.

Rozwiązanie jest jedną z minimalnych (najkrótszych) sąsiednich subarag, których suma wynosi > K.

Weź dwa indeksy, jeden na początek podtablicy i jeden na koniec (jeden za końcem), zacznij od end = 0 i start = 0. Zainicjować sum = 0; i 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; 
} 

Od obu indeksów tylko są zwiększane, algorytm jest O(n).

Answer 2

Implementacja Java dla dodatnich i ujemnych (nie całkiem pewnych liczb ujemnych) liczb, które działają w O (n) czasie z O (1) spacji.

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; 
}