最小子阵列大于键

Question

我有一个整数数组(不一定排序),我想找到一个连续的子数组,其值的总和最小,但大于特定值 K

例如:

input:array : {1,2,4,9,5},键值:10

输出: {4,9}

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

我的想法:无论如何我都找不到,O(n)但我能想到的只是O(n^2)时间的复杂性.

Answer 1

我们假设它只能有正值.

那很容易.

解决方案是最小(最短)连续子阵列之一,其总和是> K.

取两个索引,一个用于子阵列的开始,一个用于结束(一个用于结束),以end = 0和开头start = 0.初始化sum = 0;和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;
}

由于两个索引仅递增,因此算法是O(n).