Leetcode: 2 つの合計を直感的に計算するアプローチ

スポットオン チェンジ ホテル内の土産物店のオーナーになったと想像してください。レジを閉めると、8 ユーロの超過額があることに気が付きました。どうやら、客が正確なお釣りを受け取らなかったようです。これではホテルの評判が下がってしまうかもしれません。これを避けるために、間違ったお釣りの謎を解くことにしました。店のレジを開くと、2 つの異なる口座でエラーが発生していることがわかりました。

あなたは計画を立てます。各部屋を訪ねて、客に店で受け取ったお釣りを尋ね、間違った紙幣を持っている 2 人を見つけるまで続けます。1 階に到着すると、客はお釣りで 4 ユーロを受け取ったと報告します。あなたは、4 ユーロに足すと 8 になる数字を見つける必要があると計算します。2 階に移動すると、客のお釣りは 5 ユーロです。4 + 5 は 9 なので、ここではないはずです... 5 階、6 階... 10 階、ダメ、ダメ、ダメ!

最初の試みで値が見つからなかったため、2 階に降りて、すべてのゲストにもう一度お釣りを尋ね、次の開始階の値と比較します。これは疲れる作業ですよね。コンピューター サイエンスでは、この検索方法はブルート フォースと呼ばれ、配列内の 1 つの項目を次の項目と比較する非常に遅い検索方法です。

これは時間がかかり、効率的ではありません。Spot-On Change Hotel のすべてのフロアを何度も上り下りすることを想像してみてください。これはあなたにとっても、またコンピュータにとっても現実的ではありません。

ソフトウェア プログラムでこの階の上り下りがどのように行われるか知りたい場合は、JavaScript で次のように記述します。

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

冷静に状況を評価した後、間違ったお釣りを持っている 2 人のゲストを見つけるより効率的な方法があることに気づきます。

9 ユーロは x + y に等しいという最初の数学的直感を洗練させます。少し計算してみると、x + y = 9 は y = 9 — x と同じであり、検索の効率を高める際に大きな違いを生むことがわかります。

戦略を変更したもう 1 つの点は、ゲストが伝えた値をメモ帳に書き留めるようになったことです。これにより、ゲストに同じ値を 2 回尋ねる必要がなくなり、階段を上り下りするのに 1 日を費やす必要がなくなります (エレベーターが故障したら最悪です)。

新しい道具を手にして 1 階へ向かいます。そこでは、客がお釣りが 5 ユーロあると言います。これを {5: 0} と記録します。これは、位置 0 の値が 5 であることを示します。方程式で x を 5 に代入して、y = 8–5 を計算すると、y = 3 になります。メモ帳はまだ空なので、結果 8 を得るための 5 の補数である 3 は記録されていません。次に、メモ帳に 5 という数字を書き留めます (常にその時点で確認された数字を書き留め、その補数は書き留めないことを忘れないでください。補数は、書き留めた目標の数字と比較するためにのみ使用します)。2 番目の客のところへ進みます。その客は、お釣りが 2 ユーロあると言います。もう一度式を適用します: y = 8–2 => y = 6、記録を確認しますが、6 という数字は見つかりません。したがって、記録に 2 を追加します。これで {5: 0, 2: 1} になります。検索を続けると、次のゲストが 3 ユーロのお釣りを受け取ったと報告します。もう一度計算します: y = 8–3 => y = 5。ビンゴ! メモ帳に 5 が記録されています! 0 階のゲストは 2 階のゲストの補数です! このアプローチはハッシュ テーブルと呼ばれ、あなたとコンピューターの両方にとってはるかに高速で効率的です。JavaScript では、次のように実装されます。

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

これはLeetcodeからの簡単な問題ですが、その背後にある概念を理解して初めて簡単になります。自分で問題を解いてみて、その背後にある直感を構築し、独自のアナロジーを作成し、レビューし、解決に進む前に疑似コードを書いてみることをお勧めします。

私の例え話が、2 つの合計チャレンジの背後にある概念をよりよく理解するのに役立つことを願っています。

また次回お会いしましょう！