それぞれ長さが n の 5 つのソートされたリスト: List1、List2、List3、List4、List5 が与えられます。5 つの (int) 数値 (各リストから 1 つ) がある場合、合計が 0 になると true を返します。私の目標は、アルゴリズムが O(n) であることを確認することです。頭のてっぺんから、5 つのリンクされたリストの合計を持つハッシュ マップを作成するか、[o(n*n*n*n*n)] のように 5 つのリストを評価することを考えることができます。複雑さを最適化または軽減する方法を探していますが、行き詰まっています。
Python での私のコード:
def getIndicesFromFiveArrays(List1,List2,List3,List4,List5,t):
a,b,c,d,e=0,0,0,0,0
while(List1[a]+List2[b]+List3[c]+List4[d]+List5[e]!=t):
b=b+1
if b==len(List2):
return (-1,-1)
if List1[a]+List2[b]+List3[c]+List4[d]+List5[e]<t:
a=a+1
b=b-1
c=c-1
d=d-1
e=e-1
if a==len(List1):
return (-1,-1)
return (a,b,c,d,e)
編集 1: ちなみに、これは宿題ではありません。他の質問を確認して、自分で確認してください。ありがとう..