Minimum Subarray which is larger than a Key

问题:

I have an array of integers (not necessarily sorted), and I want to find a contiguous subarray which sum of its values are minimum, but larger than a specific value K

e.g. :

input : array : {1,2,4,9,5} , Key value : 10

output : {4,9}

I know it's easy to do this in O(n ^ 2) but I want to do this in O(n)

My idea : I couldn't find anyway to this in O(n) but all I could think was of O(n^2) time complexity.

回答1:

Let's assume that it can only have positive values.

Then it's easy.

The solution is one of the minimal (shortest) contiguous subarrays whose sum is > K.

Take two indices, one for the start of the subarray, and one for the end (one past the end), start with end = 0 and start = 0. Initialise sum = 0; and 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;
}

Since both indices only are incremented, the algorithm is O(n).

回答2:

Java implementation for positive and negative(not completely sure about the negative numbers) numbers which works in O(n) time with O(1) space.

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