私はソートされたリストと整数をとり、リスト内の要素のペアの合計が整数に等しいかどうかをチェックする関数をPythonで書く必要があります。また、線形時間(またはO(n)時間)で実行する必要があります。私はタスクを完了する機能を持っていますが、それは二次的な時間で実行されます。ここに私の機能は次のとおりです。一緒に追加された要素のペアが別の整数と等しいかどうかを確認し、それが線形時間で実行されるようにする関数をとる方法?
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()
私はこの実行を行うために線形時間で、私は2番目のforループを削除する必要があることはかなり確信しているが、私は、私はせずにリストを通過することができる方法のわからないんだけど2番目のループ。とにかく私はこの機能を簡素化することができます&それは線形時間で実行するには?どんな助けでも大歓迎です。読んでくれてありがとう。