처음으로 Java를 활용해서 풀어보았습니다. 스프링 부트 개발자를 지향하기에 활용하는 언어에 익숙해지는게 우선이라 생각했어요. 그럼 시작하겠습니다.

문제

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.

제한사항

• $2$ <= nums.length <= $10^4$
• $-10^9$ <= nums[i] <= $10^9$
• $-10^9$ <= target <= $10^9$
• Only one valid answer exists.

기타

• Can you come up with an algorithm that is less than $O(n^{2})$ time complexity?

접근

정수가 담긴 배열과 숫자target가 주어졌을 때, 배열 요소를 합한 값이 target이 되는 2개의이배열 인덱스를 반환하는 문제입니다.

제한 및 기타사항으로 봤을 때 알 수 있는 요소가,

1. 숫자는 양수일수도 있고, 음수일수도 있다.
2. 아주 큰 숫자가 있을 수 있다.
3. 답은 하나만 존재
4. 가능한 시간 복잡도를 $O(n^{2})$보다 빠르게 해야 한다.

이를 통해 생각해낸 접근법은 배열 요소 내 숫자를 key로, 인덱스 값을 value 둔 HashMap을 사용하는 것이었습니다.

처음엔 HashMap에 미리 초기화를 하고 진행하는 방식을 생각했으나, 예제에서 봤을 때 중복된 숫자가 존재할 수 있다는 사실이었습니다.

이를 해결하기 위한 접근 방법이,

1. 순회하는 과정에서 해당 값이 존재하지 않으면 target - 현재 숫자를 key, 인덱스를 value로 HashMap에 추가합니다.
   (HashMap을 사전에 초기화하지 않아요.)
2. 이후에 현 숫자가 HashMap에 검색해서 존재하면 target - 숫자의 값을 이미 처리했단 의미가 되어 HashMap의 해당 인덱스 값과 현재 인덱스 값을 담은 배열을 반환합니다.

이 경우 for문을 한번만 수행하기 때문에 기본 로직 시간 복잡도는 O(n)이 되나 중간에 HashMap 검색과 추가의 경우 각각 최악의 경우 O(n)이긴 하나, 평균적으로 O(1)이 되므로 O($n^2$) 이하의 시간 복잡도를 기대할 수 있겠습니다.

답안

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

public class Solution {

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> checkMap = new HashMap<>();
        for(int nIndex = 0 ; nIndex < nums.length; ++nIndex){
            final int num = nums[nIndex];
            if(checkMap.containsKey(num))
            {
                return new int[]{ checkMap.get(num), nIndex };
            }

            checkMap.put(target - num, nIndex);
        }

        return new int[]{-1, -1};
    }
}