[Java-알고리즘] Two Sum

[Problem]

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

 

[Example1]

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

 

[Example2]

Given nums = [3, 2, 4], target = 6,

Because nums[1] + nums[2] = 2 + 4 = 6,
return [1, 2].

 

[Solution 1]

class Solution {
    public int[] twoSum(int[] nums, int target) {
       for(int i = 0; i < nums.length - 1; i++){
           for(int j = i+1; j < nums.length; j++){
               if(nums[i] + nums[j] == target){
                   return new int[]{i, j};
               }
           }
       }
        
        return null;
    }
}

 

 

 

해당 문제를 풀기 위한 방법 중 가장 먼저 생각난 방법인 배열 전체 탐색 방법이다. 일명 brute force 방법으로 수행 시간은 아마 O(N^2)으로 비효율적이다.

 

[Solution 2]

class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map<Integer, Integer> num = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            num.put(nums[i],i);
       }
        
        for(int i =0; i < nums.length; i++){
            int complement = target - nums[i];
            if(num.containsKey(complement) && num.get(complement) != i){
                return new int[] {i, num.get(complement)};
            }
        }
        return null;
    }
}

 

 

다음 해결방법은 해쉬맵을 이용한 방법이다. 원소의 값을 키값으로 가지고 인덱스를 값으로 가지는 해쉬 맵을 만들어준다. 해쉬 맵은 키 값으로 값을 가지고 올떄 O(1) 이므로, 전체 수행 시간은 해쉬 맵을 초기화하는 O(n) + O(1)  = O(n) 이 걸리게 된다. 속도적인 측면에서 Solution 1보다 더 많이 개선되었다.

 

[Solution 3]

class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map<Integer, Integer> num = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int complement = target - nums[i];
            if(num.containsKey(complement)){
                return new int[]{i, num.get(complement)};
            }
            num.put(nums[i],i);
       }
        
        return null;
    }
}

 

 

다음 해결방법은 Solution2 에서 사용한 해쉬 맵을 다시 사용하는 방법이다. 이번에는 해쉬 맵을 초기화하는 과정과 동시에 조건에 맞는 값을 찾도록 구현했다. Solution2와 동일하게 O(n) 시간이 걸린다.