自力で解けるようになるまでLeetCodeの解法勉強3日目:問題1.Two-Sum(簡単/JavaScript)

はじめに: 私は元会計士からソフトウェア エンジニアに転向し、2022 年 1 月にコーディング ブートキャンプを卒業しました.現在、ほとんどのテック企業にとって、アルゴリズムとデータ構造は面接の避けられない部分です.そして、私の友人の 1 人が、トップ テクノロジー企業に入るためには、60 秒以内にミディアム リートコードの問題を解決する必要があると教えてくれました.

どの問題も (簡単な問題であっても) 解決方法がわからないので、何時間も無駄にして、それを理解することができないと思いました.これが私のアプローチです:

リートコードの問題をランダムに選択するか、対象の企業からオンライン評価を選択します.

Youtube または LeetCode のディスカッション セクションから 1 ～ 2 のソリューションを学習します. 1 つのブルート フォース ソリューション、もう 1 つはより最適なソリューションです.

詳細な説明をブログに投稿し、ソリューションをよりよく理解できるように口頭で説明します.

ソリューションを見ずに LeetCode でソリューションをコーディングする

忘却曲線と戦う: 次の 3 日間、質問をやり直します.そして、定期的に戻って問題を再検討してください.

問題＃1。ツーサム

Difficulty: Easy Language: JavaScript
整数 nums の配列と整数 target を指定すると、合計が target になるような 2 つの数値のインデックスを返します.

各入力には正確に 1 つのソリューションがあり、同じ要素を 2 回使用しないと想定することができます.

任意の順序で回答を返すことができます.

例 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

例 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

例 3:

Input: nums = [3,3], target = 6
Output: [0,1]

制約:

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

有効な回答は 1 つだけです.

フォローアップ: O(n2) 時間の複雑さよりも少ないアルゴリズムを考え出すことができますか?

解決策 1 (ネストされたループ) と説明:

var twoSum = function(nums, target) {

    for (i = 0; i < nums.length; i++) {

/*Loop through nums array (note 1) from position 0*/

        for (j = i + 1 ; j < nums.length; j++)

/*Loop through nums array (note 1) from position 1 and add up
every possible pair of numbers until they add up to target number.
*/

            if(nums[i] + nums[j] == target)

/*For example, if nums = [2,3,4], the possible pairs would be 2+3,
2+4 (starting from first number 2 add the next numbers). That was
all pairs with the number 2. Then pair 3+4 (starting from second
number 3, add the next numbers).*/

                return [i, j]

/*return indices for the pairs found*/

    }
};

解決策 1 提出の詳細 (2022 年 2 月 11 日現在)
(以下のデータは、毎日新しい提出物があるため、異なる場合があります)

ランタイム: ランタイム: 224 ミリ秒

メモリ使用量: メモリ使用量: 42.5 MB

解決策 2 (オブジェクト) と説明:

var twoSum = function(nums, target) {
    let hash = {};

/*create a object (note 2) and utilize object's property value and
property key*/

    for(let i = 0; i < nums.length; i++) {

/*Loop through "nums" array and find desired value to store in the
"hash" object */

    const n = nums[i];

/*create a variable n to represent each number in the "nums"
array*/

    if(hash[target - n] !== undefined) {

/*find the complementary pair for "n" in "hash" object*/

       return [hash[target - n], i];

/*if found, return index of both the complementary pair and "n".
We can access object properties using a square bracket
object[property]*/

    }
    hash[n] = i;

/*If complementary pair for "n" is not found in "hash", store n
and its index in "hash". 

Example Input: nums = [2,7,5,11]; target = 9. The first "n" is 2
and since "hash" is initially empty, we won't find the
complementary pair（target - n）= 7 in there. Hence, we store it in
"hash" with the index of the number 2, which is 0. And now our
"hash" is { '7', 0 } (Key is'7' and value is 0 in this object).
Then we exam if complementary pair of the second number 7 can be
found in the "hash". Since we just stored 7 in the previous step,
it will be found in this step. Therefore, we return the value that
has key of '7' in the object: hash[target - n]. And the index of
second number '7':[i]. That is [0,1]. And this is the output of
this example*/

      }
}

解決策 2 提出の詳細 (2022 年 2 月 12 日現在)
(以下のデータは、毎日新しい提出物があるため、異なる場合があります)

ランタイム: 88 ミリ秒

メモリ使用量: メモリ使用量: 42.6 MB
**********************************************

参考文献:
LeetCode Problem Link
LeetCode Discussion
Note 1: For...Loop
Note 2: JavaScript Hash Table
Note 3: For...Loop

Blog Cover Image Credit