혼자서 해결할 수 있을 때까지 LeetCode 솔루션 공부 3일차: 문제#1.Two-Sum(Easy/JavaScript)

소개: 저는 전직 회계사에서 2022년 1월에 코딩 부트캠프를 졸업한 소프트웨어 엔지니어입니다. 알고리즘과 데이터 구조는 현재 대부분의 기술 회사에서 인터뷰에서 피할 수 없는 부분입니다. 그리고 내 친구 중 한 명이 최고의 기술 회사에 들어가려면 60초 미만의 중간 leetcode 문제를 해결해야 한다고 말했습니다. 그래서 나는 구직 중에 그것을 하는 방법을 배우기 시작해야겠다고 생각했습니다.

나는 어떤 문제(심지어 쉬운 문제라도)를 해결하는 방법에 대한 단서가 없기 때문에 시간을 낭비하고 알아낼 수 없다고 생각했습니다. 내 접근 방식은 다음과 같습니다.

무작위로 leetcode 문제를 선택하거나 대상 회사의 온라인 평가를 선택하십시오.

Youtube 또는 LeetCode 토론 섹션에서 1-2 솔루션을 연구하십시오. 하나의 무차별 대입 솔루션, 다른 하나가 더 최적입니다.

자세한 설명과 함께 블로그 게시물을 작성하고 솔루션을 더 잘 이해하는 데 도움이 되도록 구두 연습을 합니다.

솔루션을 보지 않고 LeetCode에서 솔루션을 코딩합니다.

망각 곡선 퇴치: 앞으로 3일 동안 질문을 다시 하십시오. 그리고 정기적으로 돌아와서 문제를 다시 살펴보세요.

문제 #1. 투썸

Difficulty: Easy Language: JavaScript
정수 배열nums과 정수target가 주어지면 두 숫자의 인덱스를 반환하여 합이 target 가 되도록 합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정하고 동일한 요소를 두 번 사용하지 않을 수 있습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

예 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

하나의 유효한 답변만 존재합니다.

후속 조치: 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일 기준)
(아래 데이터는 매일 새로운 제출이 있기 때문에 다를 수 있습니다)

런타임: 런타임: 224ms

메모리 사용량: 메모리 사용량: 42.5MB

설명이 포함된 솔루션 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일 기준)
(아래 데이터는 매일 새로운 제출이 있기 때문에 다를 수 있습니다)

런타임: 88ms

메모리 사용량: 메모리 사용량: 42.6MB
**********************************************

참조:
LeetCode Problem Link
LeetCode Discussion
Note 1: For...Loop
Note 2: JavaScript Hash Table
Note 3: For...Loop

Blog Cover Image Credit