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.

那就简单了。

解决方案是最小(最短)连续子数组之一，其总和为 > 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)。