arrays - 查找数组中 K 个连续项的最小总和

Question

给定大小为 n 的无序数组和大小为 k 的子数组，从所有连续子数组和中找出最小和。

我们将有 (n-(k-1)) 个子数组

示例:

数组(n=5):5 3 0 2 5

k = 3

子数组:5 3 0, 3 0 2, 0 2 5

总和:8、5、7

最低金额:5

我的代码:

sum = 0;

    for(index=0; index<K; index++){

        sum = sum + array[index];
    }

    minSum = sum;

    if(N!=K){
        for(index=1; index<=(N-H); index++){

            sum = sum - array[index-1] + array[index+K-1];

            if(sum < minSum){
                minSum = sum;
            }
        }   
    }

    cout << minSum << endl; 

我的问题是:

有没有有效的代码可以做到这一点？由于 Array 有 10^5 个元素，因此需要花费大量时间。

Answer 1

据我所知，您首先创建一个窗口来计算前 K 个元素的总和，然后通过减去最左边的值并添加最右边的值来将窗口向右移动。

这是复杂度最小的解决方案。

我已经创建了一个小脚本来演示正确性以及执行较大输入所花费的时间。

http://ideone.com/pS7Sp5

array = (5,3,0,2,5)
K = 3
N = len(array)


def findMin(array, sub_array_size):
    sum = 0;

    for index in range(K):
        sum = sum + array[index];

    minSum = sum;

    if N != K:
        for index in range(1,(N-K)+1):
            sum = sum - array[index-1] + array[index+K-1];

            if(sum < minSum):
                minSum = sum
    return minSum

print(findMin(array,3))
print(findMin([1,0]*100000,3))