JavaScript의 상징적인 Two Sum

오늘 포스팅에서는 대표적인 코딩 챌린지인 Two Sum을 풀어보겠습니다 . 대부분의 사람들에게 이 문제는 상당히 사소하지만 다른 사람들에게는 시작하기에 좋은 곳이며 특정 데이터 구조의 장점을 실제로 예시합니다. 이 기사에서 단계별 솔루션과 분석을 살펴보겠습니다.

LeetCode는 코딩 문제에 대한 훌륭한 소스입니다.

투썸

'정수 배열 nums과 target두 숫자 의 정수 반환 인덱스가 주어지면 target'- 이 문제의 변형을 얻을 수 있지만 일반적으로 정수 목록이 포함되며 '목표'가 주어집니다. 도달할 가치. 목표 값은 목록에서 정수 2개를 더하여 구성됩니다.

이 문제를 좀 더 간단하게 만들기 위해 부과할 몇 가지 제약 조건은 다음과 같습니다.

유효한 답은 하나만 존재합니다. 예: [1, 3, 5, 2, 12], 7. 5 + 2만 7이 됩니다. [4, 3, 5, 2, 12]와 같은 배열은 4 + 3 또는 5 + 2로 입력으로 주어지면 둘 다 유효한 출력입니다.
정수는 한 번만 사용할 수 있습니다(예: [ 1, 2, 3, 5 ], 6). 유효한 유일한 출력은 5 + 1이며, 3은 3 + 3으로 두 번 사용할 수 없습니다.

// Some test cases to try out on your own
const twoSum = (array, target) => {
// insert your solution here
}
const arr1 = [3, 4, 5, 6, 7]; 
const target1 = 8;
// should return, [0,2] > 3 + 5 = 8
const arr2 = [34, 23, 35, 24, 2, 7, 11]
const target 2 = 47;
// should return, [1, 3]
const arr3 = [7,7]
const target3 = 14
// should return [0,1]

이것의 무차별 대입 방법은 중첩 루프를 만드는 것입니다. 매우 간단합니다. 주어진 배열의 각 요소(n)를 반복하고 와 같은 값을 찾는 또 다른 루프를 만듭니다 target — n . 아래와 같이 보일 것입니다.

const twoSum = (array, target) => {
     for ( let i = 0; i < array.length; i++) {
          for ( let j= i++; i< array.length; j++) {
               if ( array[j] === target - array[i]) return [i, j]               
          };
     };
     return null;
};

2패스 및 싱글패스 접근 방식

다음 솔루션 은 해시 테이블을 사용합니다. 해시 테이블 및 그 용도에 대한 검토는 여기 에서 제 기사를 참조 하십시오 . 해시 테이블은 우리가 찾고 있는 '키'를 알고 있는 한 삽입, 삭제 및 검색이 모두 O(1) 시간에 실행되기 때문에 이 문제에서 사용할 수 있는 매우 유용한 데이터 구조입니다.

2단계 솔루션에서는 테이블을 요소: 인덱스 쌍으로 채울 것입니다. 두 번째 루프는 해시 테이블이 complement = target — hashtable[i]존재 하는지 확인하고 인덱스를 반환하고, 그렇지 않으면 num을 반환합니다.

const twoSum = (array, target) => {
     const hashtable = {};
    for ( let i = 0; i < array.length; i++) {
       hashtable[nums[i]] = i;   
     };
     for ( let j= 0; j< array.length; j++) {
        let complement = target - array[j]
// The second condition checks for cases like twoSum([7,7], 14) where the indices of similar elements MUST be different
        if ( hashtable.hasOwnProperty(complement) &&      
        hashtable[complement] !== j) {
             return [hashtable[complement], j]
        }
     };
     return null;
};

위의 솔루션은 보완을 확인하고 해시 테이블에 요소와 인덱스를 한 번에 추가할 수 있으므로 단일 패스 알고리즘에 더욱 최적화될 수 있습니다.

const twoSum = (array, target) => {
     const hastable = {};
     for ( let i = 0; i < array.length; i++) {
        let complement = target - array[i];
       
        if ( hashtable.hasOwnProperty(complement)){
          return [hashtable[complement], i]
        }
 
        hashtable[array[i]] = i;   
     };
     
     return null;
};

데이터 구조 시리즈가 끝나감에 따라 저는 몇 가지 인기 있는 코딩 문제를 다루고 제가 탐구하고 있는 새로운 기술에 대해 글을 쓸 것입니다.