Mindest Subarray, die größer als ein Schlüssel

Question

ist ich ein Array von ganzen Zahlen (nicht unbedingt sortiert), und ich möchte einen zusammenhängenden Sub-Array zu finden, die Summe seiner Werte sind Minimum, aber größer als ein bestimmter Wert K

z.B :

Eingang: Array: {1,2,4,9,5}, Schlüsselwert: 10

Ausgang: {4,9}

Ich weiß, es ist einfach, dies in O(n^2) zu tun, aber ich will die

Meine Idee in O(n) tun: Ich konnte sowieso nicht in O(n) zu diesem Thema finden, aber alles, was ich denken konnte, war von O(n^2) Zeitkomplexität.

Answer 1

Nehmen wir an, dass es nur positive Werte haben kann.

Dann ist es einfach. Die Lösung ist eine der kleinsten (kürzesten) zusammenhängenden Subarrays, deren Summe > K ist.

Nimm zwei Indizes, einen für den Beginn des Subarrays und einen für das Ende (einen nach dem Ende), beginne mit end = 0 und start = 0. Initialisiere sum = 0; und 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; 
} 

Da beide Indizes nur erhöht werden, ist der Algorithmus O(n).

Answer 2

Java-Implementierung für positive und negative Zahlen (nicht ganz sicher über die negativen Zahlen), die in O (n) -Zeit mit O (1) -Raum arbeiten.

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