[해시맵 (HashMap)] LC #1 Two Sum

문제 설명

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

문제 링크: https://leetcode.com/problems/two-sum/

1. 문제의 핵심: 해시맵(HashMap)을 이용한 O(N) 탐색

이 문제는 배열에서 두 숫자의 합이 특정 값(target)이 되는 조합을 찾는 가장 기본적인 문제입니다. 무작정 모든 쌍을 비교하는 O(N2) 방식은 비효율적이며, 문제의 Follow-up에서 O(N2)보다 더 나은 시간 복잡도를 요구합니다.

핵심 아이디어: 각 숫자를 순회하면서, target - 현재 숫자 (즉, complement)가 이전에 등장했는지 해시맵을 통해 빠르게 확인한다. 해시맵에는 숫자 -> 인덱스 형태로 저장하여, complement를 찾았을 때 그 인덱스를 바로 알 수 있도록 한다.

2. 해결 전략

  1. Integer 값을 키로, 해당 값의 Integer 인덱스를 값으로 저장할 HashMap을 생성합니다.
  2. 주어진 nums 배열을 처음부터 끝까지 순회합니다.
  3. 각 숫자 nums[i]에 대해, complement = target - nums[i]를 계산합니다.
  4. HashMap에 complement가 존재하는지 확인합니다.
    • 만약 존재한다면, 현재 i와 HashMap에 저장된 complement의 인덱스를 배열로 만들어 반환합니다.
    • 만약 존재하지 않는다면, 현재 숫자 nums[i]와 그 인덱스 i를 HashMap에 저장합니다.
  5. 문제 조건에 따라 항상 하나의 유효한 해답이 존재하므로, 루프가 끝까지 실행될 일은 없으며, 항상 중간에 해답을 찾아 반환하게 됩니다.

3. Java 코드 구현

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map numMap = new HashMap<>(); // 숫자를 키로, 인덱스를 값으로 저장

        for (int i = 0; i < nums.length; i++) {
            int currentNum = nums[i];
            int complement = target - currentNum;

            // complement가 맵에 존재하는지 확인
            if (numMap.containsKey(complement)) {
                // 존재한다면, 현재 인덱스와 complement의 인덱스를 반환
                return new int[]{numMap.get(complement), i};
            }

            // 존재하지 않는다면, 현재 숫자와 인덱스를 맵에 추가
            numMap.put(currentNum, i);
        }

        // 문제 조건에 따라 항상 하나의 해답이 존재하므로, 이 부분은 실행되지 않음
        return new int[]{-1, -1}; // 예외 처리 또는 오류 반환
    }
}

💡 코드 세부 포인트