Javascript의 Two Sum 문제

일반적인 아이디어

Two Sum 문제는 고전적인 알고리즘 문제입니다. 제공된 특정 *타겟 *에 추가되는 두 개의 숫자를 배열에서 찾은 다음 주어진 배열에서 해당 인덱스를 반환하도록 요청합니다.

문제 설명

정수 배열 nums와 정수 목표가 주어지면 목표에 합산되는 두 숫자의 인덱스를 반환합니다. 각 입력에는 정확히 하나의 솔루션이 있으며 동일한 요소를 두 번 사용할 수 없습니다.

입력: 숫자 = [2, 7, 11, 15], 대상 = 9
출력: [0, 1]
설명: nums[0] nums[1] = 2 7 = 9

접근 방식 1 무차별 대입

모든 문제에 대한 첫 번째 접근 방식은 개념적으로 가장 쉬운 일을 완료하는 것일 수 있습니다.

두 개의 루프로 배열을 반복하고 모든 숫자 쌍을 확인합니다.

const twoSum = (nums, target) => {
  for(let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      console.log(` i is ${nums[i]} and k is ${nums[j]}`)
      // lets check if we add the 2 numbers if it equals target
      if (target === nums[i] + nums[j]) {
        return [i, j]
      }
    }
  }
};

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

접근법 1 복잡성

시간 복잡도는 O(n²)

입니다.

1. 모든 숫자 쌍을 검사하는 중첩 루프
2. 가능한 모든 조합을 확인합니다
3. 큰 배열의 경우 속도가 매우 느려짐

공간 복잡도는 O(1)
입니다. 1.새로운 데이터 구조를 생성하지 않았습니다

접근 방식 2 더 효율적이고 우리가 원하는 것.

이 문제를 해결하기 위해 해시 맵을 사용하겠습니다. 이 알고리즘을 조금 설명해보자

1. 우리는 해시 맵(JavaScript의 개체)을 사용하여 본 숫자를 저장합니다
2. 각 숫자에 대해 보수(목표 - 현재 숫자)를 계산합니다
3. 우리 맵에 보완물이 존재하는지 확인합니다
4. 그렇다면 두 숫자를 찾아서 그 색인을 반환합니다
5. 그렇지 않은 경우 현재 번호를 지도에 추가합니다

첫 번째 해결책은 일반 JS 객체를 사용하여 HashMap을 그런 식으로 구축하는 것입니다

const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i] 

    if (complement in objectStuff) {
      return [objectStuff[complement],i]
    }
    objectStuff[nums[i]] = i 
  }
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimizedRegularObject(nums, target));

두 번째 솔루션은 실제로 JS의 Map 데이터 구조를 사용하는 것입니다. 이는 Map 객체(ES6에 도입됨)를 사용하여 더 엄격하고 강력한 구현을 허용하며 종종 선호됩니다. 맵은 명시적인 해시 맵 동작을 제공하고 Object.prototype에서 속성을 상속하는 것과 같은 JavaScript 개체의 일부 특이한 현상을 방지합니다.

const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i]

    if (mapOfStuff.has(complement)) {
      return [mapOfStuff.get(complement), i]
    }
    mapOfStuff.set(nums[i], i)
  }

}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimized(nums, target));

접근법 2 복잡성

시간 복잡도는 O(n)

입니다.

1. 배열을 통한 단일 패스
2. 해시 맵은 O(1) 조회를 제공합니다
3. 총 시간은 배열 크기에 따라 선형적으로 확장됩니다

공간 복잡도는 O(n)
최악의 경우 거의 모든 숫자를 저장할 수도 있습니다
시간과 메모리 효율성 사이의 균형

주의사항

1. 빈 배열
2. 해결책이 없습니다
3. 다양한 솔루션이 가능합니다. 이 경우 1차 반복 후 복귀 여부를 문의해 주세요.

위 내용은 Javascript의 Two Sum 문제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!