配列検索の擬似コード - 配列、アルゴリズム、擬似コード

質問：

「配列Aと整数値kを指定して、Aに2つの異なる整数がkとなる場合はtrueを返し、それ以外の場合はfalseを返すアルゴリズムを作成します。」

私の疑似コード：

入力：値kのサイズnの配列A

出力：Aの2つの異なる整数がkになる場合はtrue、そうでない場合はfalse

Algorithm ArraySum(A, n, k)
for (i=0, i<n, i++)
for (j=i+1, j<n, j++)
if (A[i]+A[j]=k)
return true
return false

このアルゴリズムを正しく書いたか私が見ていない間違いはありますか？

回答：

回答№1は0

2つの異なる整数が A[i], A[j] どこで i != j のではなく、 A[i] != A[j]、あなたの擬似コードは正しいです。

---

回答№2については2

問題に関して私の頭の中に2つの解決策があります。

最初の解決策

1.空のハッシュを作る
2.配列内のすべての番号をハッシュでマークする

 for each i (Array A){
hash[i] = 1;
}

3.実行するだけ O(n) ループ

for each i (Array A)
if(  hash[ k - i ] )
print "solution i and k-i"

それはあなたに与えるだろう O(n) 複雑

第二の解決策

1.ソートアレイ
2.実行する O(n) ソートされた配列をループ処理する

for each i (Array A)
binary_search( Array, k - i); [log n operation]

それはあなたに与えるだろう O(n logn) 複雑。

---

回答№3の場合は0

いくつかのケースのように見えます ナップザック問題.

あなたの場合（2つだけの数）、比較の数を減らすためにあなたの配列をソートするのが良いでしょう（A [i] + A [j] = k）。

例えば：

you have sorted array [1 3 5 8 10 12 14 20 50 60 100]
sum of two numbers must be equal to 30

それからあなたは書くことができます

 while(a[i] <= 30) {
while(a[i] + a[j] <= 30) {
// ...
i++;
j++;
}
}

---