[LeetCode] Two Sum (Java)

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

문제

 

 

풀이 1

가장 간단한 방법으로, brute force 방식으로 문제를 풀이하였다.

배열 내 가장 첫번째숫자부터 기준으로 잡고 돌면서 해당 숫자와 더해서 target 수가 되는 수가 있는지 체크하고, 있다면 해당 index를 반환하는 방식으로 이중 for문을 사용하였다.

이렇게 하면 시간복잡도가 O(n^2) 라서 효율적이지는 않다.

 

코드 1

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

 

 

풀이2

조금 더 효율적으로 풀 수 있는 방법으로는, HashMap을 사용하는 방법이 있다.

HashMap 내에 target 수를 만들 수 있는 수, 즉 보수를 key로 입력하고, value에는 해당 인덱스를 입력한다.

그리고 for 문을 돌면서 해시맵 내에 해당 수가 있는지 확인 후 보수가 존재한다면 인덱스 두가지를 반환한다.

이렇게 하면 한번에 진행할 수 있으므로 for문을 한번만 사용하여 시간복잡도 O(n)만에 해결할 수 있다는 장점이 있다.

 

코드2

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

Runtime: 3 ms, faster than 88.52% of Java online submissions for Two Sum.

Memory Usage: 46.3 MB, less than 14.50% of Java online submissions for Two Sum.

 

 

 

HashMap을 사용해서 더 효율적으로 풀 수 있는 방법을 기억해두자.

그리고 해시맵 내에서 해당 키를 가지고 있는지 확인할 때는 map.containsKey() 함수를 사용하면 된다는 것도 기억하자.