最小子阵，它比一个较大的关键 [英] Minimum Subarray which is larger than a Key

问题描述

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

例如。

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

输出： {4,9}

我知道这是很容易做到这一点为O（n ^ 2），但我想这样做的 O（N）

我的想法：我找不到反正这 O（N），但所有我能想到的是为O（n ^ 2 ）时间复杂度。

解决方案

  

让我们假设它只能有正值

然后，它很容易。

解决的办法是最小（最短）连续的子阵列，其总和＆GT之一;氏/ code>。

取两个指标，一个是子数组的开始，一个是结束（一个过去的结束），开始与结束= 0 和启动= 0 。初始化总和= 0; 和分=无穷大

 ，而（完＆LT; arrayLength）{
    而（完＆LT; arrayLength和放大器;＆安培;总和＆LT; = K）{
        总和+ =阵列[结束];
        ++结束;
    }
    //现在你有一个连续的子阵的额头＆GT; K，或者到底是过去的数组的末尾
    而（总和 - 阵列[开始]＆GT; K）{
        总和 -  =阵列[开始]。
        ++启动;
    }
    //现在，你有一个_minimal_连续的子阵的额头＆GT; K（或结束已经过去的结束）
    如果（总和＆GT; K＆安培;＆安培;总和＆LT;分）{
        分= SUM;
        //存储开始和结束时，如果需要的
    }
    //取出子阵列的第一个元素，以使下轮开始
    //数组，其总和为＆lt; = K，对于最终指数必须增加
    总和 -  =阵列[开始]。
    ++启动;
}
 

由于这两个指数只有递增，算法 O（N）。

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.

解决方案

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

这篇关于最小子阵，它比一个较大的关键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！