[LeetCode] Two Sum

문제

 

풀이 1: 완저탐색

완전탐색으로 문제를 풀 수 있지만 효율적이지 못하다.

데이터의 크기는 10000이고 완전탐색의 경우 O(n^2)이므로 아슬아슬하게 통과한다.

 
import java.util.HashMap;
import java.util.Map;
 
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i=0; i<nums.length; i++) {
            for (int j=i+1; j<nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
        return null;
    }
}
 

풀이2: Hash Table 이용하기

해시맵을 사용하면 for문을 한번만 사용하기 때문에 O(N)으로 시간복잡도를 낮출 수 있다.

hash table에서 데이터 조회는 O(1)의 시간을 갖는다.

해시맵을 이용하여 요소값과 인덱스를 매핑하여 저장할 수 있다.

따라서 한 번만 순회하면서 두 요소의 합이 target값이 되는 경우를 찾을 수 있다.

 
import java.util.HashMap;
import java.util.Map;
 
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
 
        for (int i=0; i<nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[1] =map.get(target - nums[i]);
                result[0] = i;
                return result;
            }
 
            map.put(nums[i], i);
        }
        return result;
    }
}