[LeetCode] Two Sum - Java

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

Two Sum - LeetCode

처음 문제를 봤을 땐, 난이도도 Easy이고 문제 번호도 1번이어서 워밍업 문제라고 생각했다. 그래서 그 때는 바로 떠오르는 대로 이중 for문을 사용해서 풀이를 했었는데, Solution을 보니 hash table을 사용하여 해결하는 방법이 있어서 정리 해 둔다.

이런 걸 보면, 사소한 곳에서도 자료구조의 적절한 선택이 참 중요한 것 같다.

 

방법 1 : Two-pass Hash Table

1. 정수 배열 nums를 순회하며 주어진 정수 nums[i]와 그 index i 를 Map에 key 와 value로 저장한다.
2. 다시 주어진 array를 순회하며 target  - nums[i]를 Key로 갖는 Entity가 있는지 확인한다.
   • 이 때, 같은 entity를 다시 선택한 것인지 중복 확인을 해야 한다. 
3. 2에서 해당 entity가 존재 할 경우, 현재 순회중인 index i와 탐색된 key의 value를 return 한다.

소스코드

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

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (map.containsKey(key) && map.get(key) != i) {
                return new int[] {i, map.get(key)};
            }
        }
        // 도달해서는 안 된다.
        return new int[] {-1, -1};
    }
}

 

방법 2 : One-pass Hash Table

방법 1의 1에서는 미리 map에 주어진 숫자들을 넣어주는데, 여기서는 map에 우리가 찾는 entity가 있는지 확인을 먼저 하고, 없으면 key-value를 추가하는 방식을 사용한다.

map에 미리 어떤 값을 셋팅 해 두고 순회를 도는게 아니라, 빈 map에서 시작하여 같은 entity 중복되어 검출되는 것을 일일이 확인 해 주지 않아도 되므로 불필요한 연산이 줄어든다.

소스코드

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

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (map.containsKey(key)) {
                return new int[] {map.get(key), i};
            }
            map.put(nums[i], i);
        }
        // 도달해서는 안 된다.
        return new int[] { -1, -1 };
    }
}