Wie man eine Funktion nimmt, die überprüft, ob ein Paar Elemente zusammen eine andere Ganzzahl bildet und es in linearer Zeit laufen lässt?

Question

Also muss ich eine Funktion in Python schreiben, die eine sortierte Liste und eine ganze Zahl nimmt und prüft, ob die Summe irgendeines Paares von Elementen in der Liste gleich der Ganzzahl ist. Es muss auch in linearer Zeit (oder O (n) -Zeit) laufen. Ich habe die Funktion, die Aufgabe zu vervollständigen, aber sie läuft in quadratischer Zeit. Hier ist meine Funktion:

def sum_to_int(l, k): 
    Lst=sorted(l) 
    for i in range(len(Lst)): 
      for n in Lst[i:]: 
        print(Lst[i]+n==k) 

def main(): 
    l=[1, 2, 3, 4, 5, 6] 
    k=10 
    sum_to_int(l, k) 

if __name__=="__main__": 
    main() 

Ich bin ziemlich sicher, dass, um diesen Lauf in linearer Zeit zu machen, ich die zweiten for-Schleife zu entfernen, aber ich bin mir nicht sicher, wie ich durch die Liste gehen kann, ohne die zweite Schleife. Gibt es auf jeden Fall kann ich diese Funktion vereinfachen & es in linearer Zeit laufen lassen? Jede Hilfe würde sehr geschätzt werden. Danke fürs Lesen.

Answer 1

Mein Code ist wahrscheinlich nicht genau Python, da ich mit Python nicht so gut umgehen kann. Wenn jemand einen netten Code zur Verfügung stellen kann, der das selbe macht, können Sie ihn auch bearbeiten :). Wie auch immer, die Grundidee ist folgende:
Für jedes Paar von Werten aus der Liste, wenn ihre Summe kleiner als der gesuchte Wert ist, versuchen wir den nächst größeren Wert für den kleineren des Paares. Wenn ihre Summe größer als der gesuchte Wert ist, versuchen wir den nächst kleineren Wert für den größeren Wert des Paares. Sonst haben wir eine Übereinstimmung gefunden und können entweder mit dem nächsten Paar in der Liste beenden oder versuchen. Dies läuft in O(n).

def find_sum(ls, k): 
    l, u = 0, len(ls) - 1 
    while l < u: 
     sum = ls[l] + ls[u] 
     if sum == k: 
      print("Found: {} + {} = {}".format(ls[l], ls[u], k)) 
      l += 1 
      u -= 1 
     elif sum < k: 
      l += 1 
     else: 
      u -= 1 

Z. B .:

l = [1, 3, 4, 9, 10, 23, 56], k = 13 

1 3 4 9 10 23 56 
1        56 = 57 => too large, reduce upper value 
1       23  = 24 => too large -=- 
1     10    = 11 => too small, try with larger value 
    3    10    = 13 => found a match, try with the next number-pair 
      4 9     = 13 => found another match 

Sie können nur auf die Tatsache verlassen, dass es im nächsten Abschnitt arbeitet und ignorieren, es sei denn, Sie in einem Beweis interessiert sind.

Wie dies im Detail funktioniert: Lassen l und u sein der Index des niedrigeren/höheren Wertes der Liste ls. Lassen Sie nun l fixieren. Dann gibt es (möglicherweise) die Indizes u1 und u2, so dass ls[l] + ls[u1] < k und ls[l] + ls[u2] > k, wobei u1 maximal und u2 Minimum ist. In dem durch u1 und u2 definierten Fenster könnte ein anderer Index sein, nennen wir ihn u', mit u1 < u' < u2. Wenn u' vorhanden ist, muss es den Wert ls[l] + ls[u'] = k enthalten, den wir melden. Sonst wird l inkrementiert und wir suchen weiter nach u' für den neuen l. Offensichtlich muss u' <= u1 gelten, da sonst die Ordnungsbeschränkung unserer Liste verletzt würde. Wenn wir l >= u1 erreichen, haben wir den Punkt erreicht, an dem keine neuen Paare mehr auftauchen können, da wir den Suchraum erschöpft haben und der Algorithmus endet.

Answer 2

Sie diese ziemlich leicht mit einem Satz tun können:

def sum_to_int(sum_value, sorted_ints): 
    s = set(sorted_ints) 
    return any((sum_value - v) in s for v in s) 

könnte es Probleme, eine Reihe zweimal unter Verwendung von zB sum_to_int(4, [2]) würde True zurückkehren, aber man konnte dieses Problem beheben, indem ein Counter von collections

mit