查找數組中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))