3

質問：

「配列 A と整数値 k を指定すると、A に合計が k になる 2 つの異なる整数がある場合に値 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

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

4

3 に答える 3

2

この問題に関して、私の心には2つの解決策があります

最初の解決策

1.空のハッシュ
を作成する 2.配列内のすべての数値をハッシュにマークする

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

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

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

それはあなたにO(n)複雑さを与えるでしょう

2 番目のソリューション

1.配列を並べ替える 2.並べ替えた配列
に対してO(n)ループを実行する

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

それはあなたにO(n logn)複雑さを与えるでしょう。

于 2012-09-25T06:29:41.717 に答える
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++;
   } 
 }
于 2012-09-25T05:19:19.550 に答える
0

2つの異なる整数が、ではなくA[i], A[j]whereを意味する場合、擬似コードは正しいです。i != jA[i] != A[j]

于 2012-09-25T05:20:13.803 に答える