[Leet code] Two Sum

배열이 주어지고 Target 값이 주어진다.
배열안의 값으로 target 값을 만들 수 있다.

target값을 만들 수 있는 배열의 두 위치를 구하여라 라는 문제다.

2가지의 풀이 방법을 찾을 수 있다.

이중 for 문을 이용하여 합을 구하는 것

위 방법은 아무래도 이중 for문을 사용해야 하므로, $O(n^2)$의 시간 복잡도를 가지게 된다.

따라서 해쉬 테이블을 이용하여 풀었다.

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        HashMap<Integer,Integer> map = new HashMap<>();
        
        int[] result = new int[2];
        
        int index = 0;
        for(int num : nums){
            if(map.containsKey(target-num)){
                result[0] = map.get(target-num);
                result[1] = index;
                break;
            }
            map.put(num,index);
            index++;
        }
        return result;
    }
}

위 방식을 이용하여 $O(n^2)$ 으로 값을 구하던 것을 $O(n)$으로 줄일 수 있다.

대다수가 $O(n^2)$으로 풀었나보다..

끝!