合計10個のリンクリスト内のノードのすべてのペアを見つけるアルゴリズムを提案できますか。私は次のことを思いつきました。
アルゴリズム：2番目のノードから始めて、各ノードをヘッドノードから前のノード（現在のノードが比較される前）まで比較し、そのようなすべてのペアを報告します。
このアルゴリズムは機能するはずですが、O（n2）の複雑さを持つ最も効率的なアルゴリズムではないことは確かです。
誰もがより効率的な解決策を示唆できますか（おそらく線形時間がかかります）。このようなソリューションでは、追加または一時的なノードを使用できます。
それらの範囲が制限されている場合（たとえば-100から100の間）、それは簡単です。
配列quant[-100..100]を作成してから、リンクリストを循環して実行します。
quant[value] = quant[value] + 1
次に、次のループでうまくいきます。
for i = -100 to 100:
j = 10 - i
for k = 1 to quant[i] * quant[j]
output i, " ", j
範囲が制限されていない場合でも、最初に値を並べ替えてから、個々の値ではなくカウントを保持することで、提案した方法よりも効率的な方法を使用できます（上記のソリューションと同じ）。
これは、リストの最初と最後に1つずつ、合計2つのポインターを実行することによって実現されます。それらのポインターの数値が合計で10になったら、それらを出力し、終了ポインターを下に移動し、開始ポインターを上に移動します。
10より大きい場合は、終了ポインターを下に移動します。少なくなったら、スタートポインタを上に動かします。
これは、ソートされた性質に依存しています。10未満は、合計を高くする必要があることを意味します（開始ポインターを上に移動します）。10より大きいということは、合計を少なくする必要があることを意味します（ポインターを下に向けます）。それらはリスト内で重複していないため（カウントのため）、10に等しいということは、両方のポインターを移動することを意味します。
ポインタがすれ違うときに停止します。
もう1つ注意が必要な点があります。これは、ポインターが等しく、値の合計が10の場合です（これは、値が5の場合にのみ発生する可能性があります）。
積に基づいてペアの数を出力するのではなく、値から1を引いた積に基づいています。これは、カウントが1の値5は実際には合計が10にならないためです（5は1つしかないため）。
したがって、リストについては：
2 3 1 3 5 7 10 -1 11
あなたが得る：
Index a b c d e f g h
Value -1 1 2 3 5 7 10 11
Count 1 1 1 2 1 1 1 1
p1を開始します。なので、これら2つの数値を出力します（上記のように、カウントの積である回数を出力します）。それはの1つのコピーです。次に、に移動します。ap2h-1 + 11 = 10NN(-1,11)p1bp2g1 + 10 > 10でそのままp1にしてb、に移動p2しfます。1 + 7 < 10に移動p1しc、で終了p2しfます。2 + 7 < 10に移動p1しd、で終了p2しfます。3 + 7 = 10(3,7)、のカウントが2であるため、のコピーを2つ出力し、、にd移動p1します。ep2e5 + 5 = 10 ただし p1 = p2、積は0×0または0です。何も出力せず、に移動p1しf、p2に移動しdます。p1 > p2ます。したがって、全体的な出力は次のとおりです。
(-1,11)
( 3, 7)
( 3, 7)
どちらが正しい。
これがいくつかのテストコードです。テストのために、7（中間点）を特定の値に強制したことに気付くでしょう。明らかに、あなたはこれをしないでしょう。
#include <stdio.h>
#define SZSRC 30
#define SZSORTED 20
#define SUM 14
int main (void) {
int i, s, e, prod;
int srcData[SZSRC];
int sortedVal[SZSORTED];
int sortedCnt[SZSORTED];
// Make some random data.
srand (time (0));
for (i = 0; i < SZSRC; i++) {
srcData[i] = rand() % SZSORTED;
printf ("srcData[%2d] = %5d\n", i, srcData[i]);
}
// Convert to value/size array.
for (i = 0; i < SZSORTED; i++) {
sortedVal[i] = i;
sortedCnt[i] = 0;
}
for (i = 0; i < SZSRC; i++)
sortedCnt[srcData[i]]++;
// Force 7+7 to specific count for testing.
sortedCnt[7] = 2;
for (i = 0; i < SZSORTED; i++)
if (sortedCnt[i] != 0)
printf ("Sorted [%3d], count = %3d\n", i, sortedCnt[i]);
// Start and end pointers.
s = 0;
e = SZSORTED - 1;
// Loop until they overlap.
while (s <= e) {
// Equal to desired value?
if (sortedVal[s] + sortedVal[e] == SUM) {
// Get product (note special case at midpoint).
prod = (s == e)
? (sortedCnt[s] - 1) * (sortedCnt[e] - 1)
: sortedCnt[s] * sortedCnt[e];
// Output the right count.
for (i = 0; i < prod; i++)
printf ("(%3d,%3d)\n", sortedVal[s], sortedVal[e]);
// Move both pointers and continue.
s++;
e--;
continue;
}
// Less than desired, move start pointer.
if (sortedVal[s] + sortedVal[e] < SUM) {
s++;
continue;
}
// Greater than desired, move end pointer.
e--;
}
return 0;
}
このバージョンではソートしておらず、値をインデックスとしてインテリジェントに使用しているため、上記のコードはすべてO（n）であることがわかります。
最小値がゼロ未満（またはメモリを浪費するほど非常に高い）の場合は、minValを使用してインデックスを調整できます（別のO（n）スキャンで最小値を見つけてから、i-minVal代わりにを使用します）i配列インデックスの場合）。
また、低から高までの範囲がメモリ上で高すぎる場合でも、スパース配列を使用できます。O（n log n）でソートし、カウントの更新を検索する必要があります。これもO（n log n）ですが、元のO（n 2）よりも優れています。二分探索がO（n log n）である理由は、単一の探索がO（log n）になるためですが、値ごとに実行する必要があります。
そして、これがテスト実行からの出力であり、計算のさまざまな段階を示しています。
srcData[ 0] = 13
srcData[ 1] = 16
srcData[ 2] = 9
srcData[ 3] = 14
srcData[ 4] = 0
srcData[ 5] = 8
srcData[ 6] = 9
srcData[ 7] = 8
srcData[ 8] = 5
srcData[ 9] = 9
srcData[10] = 12
srcData[11] = 18
srcData[12] = 3
srcData[13] = 14
srcData[14] = 7
srcData[15] = 16
srcData[16] = 12
srcData[17] = 8
srcData[18] = 17
srcData[19] = 11
srcData[20] = 13
srcData[21] = 3
srcData[22] = 16
srcData[23] = 9
srcData[24] = 10
srcData[25] = 3
srcData[26] = 16
srcData[27] = 9
srcData[28] = 13
srcData[29] = 5
Sorted [ 0], count = 1
Sorted [ 3], count = 3
Sorted [ 5], count = 2
Sorted [ 7], count = 2
Sorted [ 8], count = 3
Sorted [ 9], count = 5
Sorted [ 10], count = 1
Sorted [ 11], count = 1
Sorted [ 12], count = 2
Sorted [ 13], count = 3
Sorted [ 14], count = 2
Sorted [ 16], count = 4
Sorted [ 17], count = 1
Sorted [ 18], count = 1
( 0, 14)
( 0, 14)
( 3, 11)
( 3, 11)
( 3, 11)
( 5, 9)
( 5, 9)
( 5, 9)
( 5, 9)
( 5, 9)
( 5, 9)
( 5, 9)
( 5, 9)
( 5, 9)
( 5, 9)
( 7, 7)ハッシュセットを作成します（JavaのHashSet）（数値が十分に制限されている場合、つまり+/- 100に該当することがわかっている場合は、スパース配列を使用できます）
各ノードについて、最初に10-nがセットに含まれているかどうかを確認します。もしそうなら、あなたはペアを見つけました。いずれにせよ、セットにnを追加して続行します。
たとえば、1〜6〜3〜4〜9があります。
1-9はセットに含まれていますか？いいえ
6-4？いいえ。
3-7？いいえ。
4-6？うん！印刷（6,4）
9-1？うん！印刷（9,1）
これはミニサブセット和問題であり、NP完全です。
最初にセットを並べ替えると、評価する必要のある数値のペアが削除されます。