Pythonを使ったコーディングでのPassingCars

Question

私は来週、最初のラウンドのインタビューでコーディングの挑戦をします。人事部は、コーディングの難題プラットフォームとしてCodilityを使用すると述べた。私はCodi​​lity Lessonsを使って練習しています。

私の問題は、正確度で非常に高い得点を得ることが多いのですが、時間の複雑さを測るパフォーマンススコアは恐ろしいです（私はしばしば0％を得ます）。

はここで質問です： https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

私のコードは次のようになります。これは、O（N）であると考えられる

def solution(A): 
    N = len(A) 
    my_list = [] 
    count = 0 
    for i in range(N): 
     if A[i] == 1: 
      continue 
     else: 
      my_list = A[i + 1:] 
      count = count + sum(my_list) 
    print(count) 
    return count 

が、鉱山がOである（N ** 2）。

1. 誰かがO（N）時間の複雑さの下でこの問題を解決するにはどうすればよいですか？

2. 一般的に、アルゴリズムに関する質問を見ると、どのようにアプローチを思いついていますか？

Answer 1

ゼロが見つかるたびに、配列全体を合計しないでください。それはそれをO（n^2）にします。代わりに、見つかったすべてのゼロは、次のそれぞれについて+1を与えることに注意してください。

def solution(A): 
    zeros = 0 
    passing = 0 
    for i in A: 
     if i == 0: 
      zeros += 1 
     else: 
      passing += zeros 
    return passing