arrays - 大于键的最小子数组

Question

我有一个整数数组（不一定是排序的），我想找到一个连续的子数组，它的值之和最小，但大于特定值K

例如：

输入：数组：{1,2,4,9,5}，键值：10

输出 ：{4,9}

我知道这样做很容易O(n ^ 2)但我想这样做O(n)

我的想法：无论如何我都找不到这个，O(n)但我能想到的只是O(n^2)时间复杂度。

Answer 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).

Answer 2

正数和负数（不完全确定负数）的 Java 实现，在 O(n) 时间和 O(1) 空间内工作。

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