JavaScriptとのK補完的なペア
私は最近、私が本当に賞賛し、いつか一緒に仕事をしたい会社のためにコードの挑戦を受ける機会がありました。 コードの課題には多くの未知数が入っていたので、私は感謝し、興奮し、さらに心配しました。 現実には、あなたが準備するためにできることはあまりありません:
- プロジェクトを構築する
- アルゴリズムを研究する
- 問題を粉砕する: LeetCode,HackerRank,CodeSignal
しかし、あなたが準備ができているかどうかを把握する唯一の方法は、あなたが浮くことができるかどうかを確認するために深い端に飛び だから私はやった、と私は今まで持っていたよりもはるかに多くを学び、そのために私はそれを共有したいと思いました。
割り当ての開始時に、私は完了するために三つのタスクに直面しました。 私はこのブログでこれらのうちの1つだけに焦点を当てます—K-相補的なペア。
目標
- ターゲット整数と正の整数でいっぱいの配列が与えられています
- ターゲット整数の補数を見つけて見つける必要があります。
numberArray+numberArray= 7
これらの2つの値がターゲットと等しいため、上記は有効なペアになります。
最初のアプローチ
私が最初にこの問題に近づいたとき、私はブルートフォースの方法でそれを追いかけました。 と思ったのに使用入れ子ループをチェックのための補足こんにちはした。 それは実際に働いた:
それはどのように動作しますか？
- 最初の配列の要素をループします。
- その後、それを一斉にループして、各パスを介してターゲットと等しいかどうかを調べます。
- ターゲットが一致している場合、カウントはインクリメントされます。
それは動作し、私はターゲットを与えられた相補的なペアの正確なカウントを受け取りましたが、それは理想的ではありませんでした。 現実には、ネストされたループは遅く、要素の大きな配列が与えられると指数関数的に成長する可能性があります。 その時間の複雑さはO（N2）です。
第二のアプローチ—最適化
だから私は描画ボードに戻りました。 いくつかの調査と検討の結果、値をオブジェクト{key：value}に格納できることがわかりました。
今、これはまだ非常にトリッキーでした、特に私は以前にそれほど複雑なものを書いたことがないので。 私は新しい領域に踏み込んでいましたが、私は実際に元のアルゴリズムをO（N）に最適化することができたので興奮していました):
それはどのように機能しますか？
- 最初にnumberArrayを実行して、located_pairsオブジェクトにキーと値のペアを作成します。 このプロセスを通して、一意性と重複をチェックします。
- 次に、配置されたオブジェクトのキーを実行し、ターゲットで作成するかどうかをvetします。 そうであれば、ペア数は増加します。
