🧮

Two Sum

Two Sum - Explanation

보통 알고리즘 O(n) O(n)

Problem Summary

Given an array of numbers and a target, return the indices of two numbers that add up to the target.

Go to Problem →

Detailed Explanation

이 문제는 **해시맵(Map)**을 활용한 최적화 기법을 학습합니다. LeetCode의 대표적인 문제로 코딩 인터뷰에 자주 등장합니다. **브루트 포스 접근 (O(n²))** 이중 for문으로 모든 쌍을 확인하는 방법은 간단하지만 비효율적입니다. **해시맵 최적화 (O(n))** 핵심 아이디어: "target - 현재값 = 보수(complement)" 각 숫자를 볼 때, 그 숫자의 보수가 이미 Map에 있는지 확인합니다. **[2, 7, 11, 15], target=9 처리 과정** - i=0, nums[0]=2: 보수=7, Map에 없음 → Map={2:0} - i=1, nums[1]=7: 보수=2, Map에 있음! → [0, 1] 반환 **Map의 역할** - key: 숫자 값 - value: 해당 숫자의 인덱스 - 이미 본 숫자와 그 위치를 기억합니다 **왜 이 방법이 효율적인가?** - 각 요소를 한 번만 방문 (O(n)) - Map 조회는 평균 O(1) - 전체 시간복잡도: O(n) **중복 숫자 처리** [3, 3]에서 target=6인 경우도 올바르게 처리됩니다. 두 번째 3을 볼 때 첫 번째 3의 인덱스가 이미 Map에 있기 때문입니다.

Solution Code

solution.js
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

Key Concepts from This Problem

1. 해시맵(Map)
2. 보수(complement) 개념
3. 시간복잡도 최적화
4. 한 번의 순회

Common Mistakes

✗ 같은 요소를 두 번 사용하지 않도록 주의해야 합니다
✗ Map에 값을 저장하기 전에 보수를 먼저 확인해야 합니다
✗ 인덱스가 아닌 값을 반환하는 실수를 주의하세요

Hints

Hint 1: 브루트포스: 이중 for문으로 모든 쌍을 확인
Hint 2: 최적화: Map을 사용해 O(n)으로 해결
Hint 3: 각 숫자에 대해 target - 현재숫자가 이미 있는지 확인

Complexity Analysis

Time Complexity

O(n)

Grows linearly with input size

Space Complexity

O(n)

Uses memory proportional to input size

Related Tags

#알고리즘 #Map #해시
Solve Problem Other Problems