次の問題を検討してください。
ソートされていない整数の配列を指定して、x^2 + y^2 = z^2 を満たすすべてのトリプレットを見つけます。
たとえば、指定された配列が
1, 3, 7, 5, 4, 12, 13
の場合、答えは と である必要が5, 12, 13
あります。3, 4, 5
複雑さ O(n^2) の以下のアルゴリズムをお勧めします。
- 配列を降順に並べ替える O(nlogn)
- 各要素の二乗、O(n)
ここで、a = b+c となるようにソートされた配列内のすべてのトリプレット (a、b、c) を見つける問題に還元されます。
インタビュアーは、O(n^2) よりも優れたソリューションを主張していました。
ウィキペディアで 3SUM 問題を読みました。これは、配列がビット ベクトルとして表現できると仮定して、数値が [-u,u] の範囲内にある場合、O(n+ulogu) で問題を解決できることを強調しています。しかし、それ以上の説明を明確に把握することはできません。
誰かが良い例で何が起こっているのかを理解するのを手伝ってくれませんか?