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.

풀이

1. 배열 안의 2개의 수를 더해서 target이 되는 인덱스를 리턴한다.
2. key:value로 저장되는 map을 사용하여 현재 요소 값: 현재 요소의 인덱스 형태로 저장한다.
3. x + y = target이고 target - x = y이 되는 점을 이용한다.
4. map에 저장되어있는 다른 수 y가 있다면 값을 리턴한다.

수도코드

dic = dict()
for nums 배열의 처음부터 끝까지:
	if target - nums[i]가 dic에 있다면:
    	return (dic[target - nums[i]], i)
    dic에 (현재 요소 값: 현재 요소의 인덱스) 저장

return ()

Solution(Runtime: 2ms)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>(); // number: index

        for(int i = 0; i < n; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] {map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }

        return new int[] {};
    }
}

처음 생각한 풀이는 브루트 포스로 for문 두개를 돌면서 target과 일치하는 두개의 값을 찾는 방법이었다. 시간복잡도는 O(n^2)이며 44ms 소요되었다.
target - x = y를 보면서 O(n)의 풀이방법을 떠올렸다. 나머지 하나의 수가 map에 있다면 target을 만들 수 있다는 것이기 때문이다.