私は部分集合の平均を計算するのにタイムアウトを続ける

Question

私は実際のコードブロックを持っていますが、HackerEarthのオンライン裁判官はタイミングエラーを返し続けます。私はコーディングに新しいので、コードをスピードアップするためのトリックを知らない。どんな助けも大いにありがとう！

N, Q = map(int, input().split()) 
#N is the length of the array, Q is the number of queries 
in_list =input().split() 
#input is a list of integers separated by a space 
array = list(map(int, in_list)) 
from numpy import mean 
means=[] 
for i in range(Q): 
    L, R = map(int, input().split()) 
    m= int(mean(array[L-1:R])) 
    means.append(m) 

for i in means: 
    print(i) 

どのような提案もすばらしいでしょう。

Answer 1

ループ内でO(N)操作を実行しないでください。現在、スライシングと（スライス内のアイテムを合計する必要がある）コールの両方が遅いです。だから、より良いアルゴリズムが必要です。

数字のリストでいくつかの前処理を行うと、が（実際にスライスを作成して追加することなく）の値の合計を計算できることがわかります。 O(N)スペースを使用すると、O(1)時間内の各合計の計算を行うことができます（プロセス全体をO(N * Q)ではなくO(N + Q)時間とする）。

私がまとめた素早い解決方法は、itertools.accumulateを使ってリスト項目の累計を検索することです。累積合計で十分ですので、実際にアイテム自体を保存するわけではありません。

from itertools import accumulate 

N, Q = map(int, input().split()) 
sums = list(accumulate(map(int, input().split()))) 

for _ in range(Q): 
    L, R = map(int, input().split()) 
    print((sums[R] - (sums[L-1] if L > 0 else 0))/(R-L+1))