[leetcode 75] 1. Two Sum

 

정수가 들어있는 배열 nums와 정수 target이 주어졌을 경우 nums의 두 숫자를 합해 target이 나오는 nums의 두 숫자의 위치를 반환하기

정답은 정확히 하나만 존재하며 같은 배열의 요소를 두번 쓸 수 없다.

예를들어

nums = [3, 3]이고 target이 6인경우 

정답을 [0,0]혹은 [1,1]이 안된다는 이야기

 

정답 예

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

    for (int i = 0; i < nums.length; i++) {

        // target - nums[i] 가 기존 맵에 저장되어있는지 검사
        if (map.get(target - nums[i]) != null) {

            // 있는경우 해당 값의 위치롸
            output[0] = map.get(target - nums[i]);

            // 현재 값의 위치를 저장
            output[1] = i;

            break;
        }

        // map에 값과 위치를 기억
        map.put(nums[i], i);
    }

    return output;
}

 

결과를 보면 이중 for문도 릿코드상에서는 상위의 결과로 나오긴하는데

map기반의 결과가 압도적으로 빠르진 않다.

 

java HashMap의 get은 O(1)이 나오는데

put의 경우 내부의 키 공간을 늘려주는 과정에서 시간이 발생하는게 원인인건지 의문