查找数组中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; 

我的问题是：

是否有任何有效的代码在那里做到这一点？ 由于数组有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))