알고리즘 연습: 두 개의 합

이것은 내가 중첩된 for 루프를 사용하여 해결했을 때보다 더 효율적인 솔루션을 찾기 위해 해시 테이블을 사용하는 데 더 익숙해지는 데 도움이 되었기 때문에 제가 작업한 흥미로운 문제였습니다. 내 친한 친구/멘토 중 한 명이 나와 함께 작업했는데, 처음에 어려움을 겪을 때 인내심을 갖고 훌륭한 통찰력을 제공한 데 대해 그에게 많은 빚을 지고 있습니다. 알고리즘 연습에 유용한 사이트인 leetcode에서 이 문제를 발견했습니다.

문제

"정수 배열nums과 정수target가 주어지면 두 숫자의 인덱스를 반환하여 대상에 합산되도록 합니다.

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

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

예:

입력: 숫자 = [2,7,11,15], 대상 = 9
출력: [0,1]
출력: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.

입력: 숫자 = [3,2,4], 대상 = 6
출력: [1,2]

접근하다

키 값 쌍을 전달할 빈 해시 테이블을 생성합니다.

단일 for 루프를 사용하여 주어진 배열nums을 반복하고 키 값 쌍을 해시 테이블에 전달합니다. 이 테이블은 요소(키)와 해당 인덱스(값)가 됩니다. 문제는 주어진 배열에 대해 하나의 솔루션만 있다는 것이므로 해시 테이블에 대상을 구성하는 요소에 해당하는 두 개의 인덱스가 포함되어 있으면 여기서 멈출 수 있습니다. 그러나 최악의 시나리오에서 해시 테이블에는 주어진 배열nums의 모든 단일 요소가 포함됩니다.

대상에서 현재 보고 있는 요소를 빼서 차이를 파악하고 변수에 저장합니다.

다음으로, 그 키 차이가 해시 테이블에 있는지 확인하고, 그렇다면 키 차이 값과 현재 보고 있는 요소의 인덱스를 반환합니다.

키 차이가 해시 테이블에 없으면 현재 요소를 해시 테이블의 키로 할당하고 해당 인덱스를 해당 값으로 할당하고 반복을 계속합니다.

해결책

먼저 빈 개체 또는 해시 테이블을 선언합니다.
여기에서 요소와 해당 인덱스를 키 값 쌍으로 전달할 것입니다.

var twoSum = function(nums, target) {
  const mapper = {};
}

다음으로 배열을 반복하는 for 루프를 만듭니다nums.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

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

}

루프 내에서 우리는 주어진 nums[index] 에서 배열에서 현재 보고 있는 target 요소를 빼서 얻은 변수 차이를 선언합니다.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

    for (let index = 0; index < nums.length; index++) {
      let difference = target - nums[index];

  }

}

다음으로 difference가 해시 테이블 mapper에 있는 기존 키인지 확인합니다. 만약 그렇다면 우리는 mapper[difference] 그리고 우리가 있는 현재 index를 반환합니다.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

    for (let index = 0; index < nums.length; index++) {
       let difference = target - nums[index]; 

        if (difference in mapper) {
            return [mapper[difference], index]
        }

  }
}

마지막으로 해시 테이블 mapper 에 difference 가 포함되어 있지 않으면 반복 중인 현재 요소와 해당 인덱스를 사용하여 해시 테이블에 새 키 값 쌍을 할당합니다.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

    for (let index = 0; index < nums.length; index++) {
       let difference = target - nums[index]; 

        if (difference in mapper) {
            return [mapper[difference], index]
        } else {
            mapper[nums[index]] = index;
        }
  }
}

이것은 O(n^2)의 런타임이었던 중첩 for 루프를 사용하는 것보다 O(n) 런타임을 제공하는 더 효율적인 솔루션입니다. 마지막으로 기억해야 할 점은 질문이 요소 자체가 아니라 대상에 합산되는 요소의 인덱스를 반환하도록 요구한다는 것입니다.