HackerRank Sherlock und Array-Leistung

Question

Ich habe diesen kleinen Algorithmus zum HackerRank Sherlock- und Array-Test, aber das bekommt Timeouts in 2 Testfällen. Diese Testfälle erstellen riesige Listen und ich konnte nicht sehen, was in Bezug auf die Leistung falsch ist.

Das ist das Problem:

Watson gibt Sherlock ein Array AA der Länge NN. Dann bittet er ihn zu bestimmen, ob ein Element im Array existiert, so dass die Summe der Elemente auf der linken Seite gleich der Summe der Elemente auf der rechten Seite ist. Wenn keine Elemente links/rechts vorhanden sind, wird die Summe als Null betrachtet. Formal finden Sie ein ii, so dass AA1 + A + A2 ... A ... Ai-1 = A = Ai + 1 + A + Ai + 2 ... A ... AN.

Eingabeformat Die erste Zeile enthält TT, die Anzahl der Testfälle. Für jeden Testfall enthält die erste Zeile NN, die Anzahl der Elemente im Array AA. Die zweite Zeile für jeden Testfall enthält durch NN Leerzeichen getrennte Ganzzahlen, die das Array AA bezeichnen.

Ausgabeformat Drucken Sie für jeden Testfall YES, wenn ein Element im Array vorhanden ist, sodass die Summe der Elemente auf der linken Seite gleich der Summe der Elemente auf der rechten Seite ist; andernfalls drucken Sie NEIN.

Dies ist mein Code:

for turn in range(int(input())): 
    lst_size = int(input()) 
    has_equal = False 

    lst = list(map(int, input().split(" "))) 

    if lst_size > 2: 

     for i in range(lst_size): 
      sumleft = sum(lst[:i]) 
      sumright = sum(lst[(i+1):]) 

      if sumleft == sumright: 
       has_equal = True 
       break 

    if has_equal: 
     print("YES") 
    else: 
     print("NO") 

Answer 1

ich nicht tun, um die Summe bei jeder Iteration des Code verbessern könnte und es funktioniert:

for turn in range(int(input())): 
     lst_size = int(input()) 

     has_equal = False 

     lst = list(map(int, input().split(" "))) 

     sumleft = 0 
     total = sum(lst) 

     for i in range(1, lst_size): 
      sumright = 0 
      sumleft += lst[i-1] 
      sumright = total - sumleft - lst[i] 

      if sumleft == sumright: 
       has_equal = True 
       break 

    if has_equal or lst_size == 1: 
     print("YES") 
    else: 
     print("NO") 

Answer 2

eine Summe Kosten wie eine Wiederholung zu machen, müssen Sie es nur einmal machen und die Summe ajust. Sie können beispielsweise aus der Mitte der Liste starten:

def test_list(lst): 
    i = len(lst)/2 
    sumleft = sum(lst[:i]) 
    sumright = sum(lst[i+1:]) 

    if sumleft==sumright: 
     print "YES",i 

    elif sumleft<sumright: 
     print "going right" 
     while(True): 
      if sumleft==sumright: 
       print "YES",i 
       break 
      if i==len(lst)-1 or sumleft>sumright : 
       print "NO",i 
       break 
      sumleft += lst[i] 
      sumright -= lst[i+1] 
      i+=1 

    else: 
     print "going left" 
     while(True): 

      if sumleft==sumright: 
       print "YES",i 
       break 
      if i==0 or sumleft<sumright : 
       print "NO",i 
       break 
      sumright += lst[i] 
      sumleft -= lst[i-1] 
      i-=1 



lst = [40,1,5,4,6,3,2,1,4,8,7,3,81] 
test_list(lst) 

Ergebnis:

> going right 
> YES 11