저는 취업 면접을 위한 알고리즘 및 데이터 구조에 대한 지식을 연습하기 위해 LeetCode 문제를 해결해 왔으며 JavaScript 솔루션을 공유하기로 결정했습니다.
참고: LeetCode 에서도 읽을 수 있습니다.

문제

문제: N과 그 이중이 존재하는지 확인
난이도: 쉬움

정수 배열 arr이 주어지면 N이 M의 2배가 되도록 두 개의 정수 N과 M이 있는지 확인하십시오(즉, N = 2 * M).

다음과 같은 두 개의 인덱스 i와 j가 있는지 더 공식적으로 확인합니다.

i != j

0 <= i, j < arr.length

arr[i] == 2 * arr[j]

입력

예 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

예 2:

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

예 3:

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

제약

2 <= arr.length <= 500

-10^3 <= arr[i] <= 10^3

순진한 솔루션

for 루프에 중첩된 for 루프를 사용하여 해당 숫자의 double인 해당 숫자가 있는지 각 요소를 확인할 수 있습니다.

그러나 우리가 O(1)의 일정한 공간 복잡도를 가질지라도 O(n²)의 2차 시간 복잡도는 좋지 않으며 가능하면 피해야 합니다.

//JavaScript
var checkIfExist = function(arr) {
    for(let i = 0; i < arr.length; i ++) {
      const currentValue = arr[i];
      for(let j = 0; j < arr.length; j ++) {
        const possibleValue = arr[j];
        if(possibleValue === 2 * currentValue && i !== j) {
          return true;
        }
      }
    }
  return false;
};

해결 방법 1: 해시 테이블

또 다른 가능한 솔루션은 JavaScript에서 객체로 나타낼 수 있는 해시 테이블 데이터 구조를 사용하는 것입니다. 주요 이점은 저장된 각 요소를 검색하는 데 O(1)의 일정한 시간이 걸린다고 가정할 수 있으므로 빠릅니다.

또한 배열을 한 번만 탐색하여 이 문제를 해결할 수 있습니다.

for 문의 각 반복에서 현재 값이 이미 객체의 키로 존재하는지 확인합니다.

그렇다면 배열에 숫자와 그 double이 있으면 true를 반환해야 합니다.

그렇지 않은 경우 키/값 쌍을 저장합니다. 여기서 한 쌍은 현재 요소를 2로 나눈 값을 키로 사용하고 다른 쌍은 현재 요소에 2를 곱한 값을 키로 사용합니다. 키만 확인하기 때문에 각 키와 함께 저장하는 값은 중요하지 않습니다.

for 루프가 일치하는 항목을 찾지 않고 종료되면 배열에 숫자와 해당 double이 포함되지 않았으므로 false를 반환해야 합니다.

입력 배열의 크기에 따라 선형적으로 확장되는 크기의 해시 테이블을 만들었으므로 선형 공간 복잡도는 O(n)입니다.

이번에는 배열을 한 번만 탐색하므로 선형 시간 복잡도가 O(n)입니다.

//JavaScript
var checkIfExist = function(arr) {
    const hashTable = {};

    for(let i = 0; i < arr.length; i ++) {
      const currValue = arr[i];

      if(hashTable[currValue] !== undefined) {
        return true
      }
      hashTable[currValue / 2] = currValue;
      hashTable[currValue * 2] = currValue;
    }

  return false;
};

지도

이 해시 테이블 접근 방식은 지도 데이터 수집에 내장된 JavaScript를 사용하여 구현할 수도 있습니다.

사용 사례의 주요 차이점은 해시 테이블의 각 키를 문자열로 저장하는 대신 Map의 각 키를 숫자로 저장한다는 것입니다. Object는 키로 문자열과 기호만 지원하지만 Map은 객체와 모든 기본 유형을 키로 지원합니다.

해결 방법 2: 설정

해시 테이블(객체) 또는 맵을 사용할 때의 문제는 키/값 쌍을 삽입할 때 키가 필요하지만 그 값은 필요하지 않다는 것입니다.

문제를 해결하기 위해 해시 테이블 데이터 구조의 속성이 필요하지만 키/값 쌍 대신 키만 필요한 경우 Set 데이터 컬렉션을 사용하는 것이 합리적입니다.
참고: Set에 내장된 JavaScript는 고유한 값만 저장합니다.

객체 및 맵과 유사하게 O(1)의 일정한 시간 복잡도를 갖는 세트에서 값을 검색할 수 있다고 가정할 수 있습니다.

우리는 입력 배열의 크기에 따라 선형적으로 확장되는 크기의 세트를 만들었습니다. 선형 공간 복잡도는 O(n)입니다.

이전 솔루션과 마찬가지로 배열을 한 번만 탐색하므로 선형 시간 복잡도가 O(n)입니다.

//JavaScript
var checkIfExist = function(arr) {
    const set = new Set();

    for(let i = 0; i < arr.length; i ++) {
      const currValue = arr[i];

      if(set.has(currValue)) {
        return true
      }
      set.add(currValue / 2);
      set.add(currValue * 2);
    }

  return false;
};

연락 유지

내 소셜 미디어를 통해 저에게 연락하십시오. 알고리즘, 데이터 구조 및 LeetCode 문제에 대해 이야기합시다. on 또는 GitHub .

이 문제에 대한 솔루션을 공유하십시오.