[Leetcode 1/100] Two Sum - Easy

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

Two Sum - LeetCode

난이도 : Easy

난이도 easy 문제로 문제를 보자마자 바로 브루트포스 방식으로 풀었습니다. 

솔루션에는 시간복잡도가 O(n)으로 해쉬 맵을 활용한 인상적인 풀이가 있어서 공유합니다.

내 풀이

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] arr = 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){
                    arr[0] = i;
                    arr[1] = j;
                }
            }
            
        }
        return arr;
    }
}

시간복잡도 : O(n^2)
공간복잡도 : O(n)

Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<nums.length; i++){
            map.put(nums[i], i);
        }
        
        for(int i=0; i<nums.length; i++){
            int complement = target - nums[i];
            if(map.containsKey(complement) && map.get(complement) != i){
                return new int[] {i, map.get(complement) };
            }
        }
        
        throw new IllegalArgumentException("No two sum solution");
    }
}

시간복잡도 : O(n)
공간복잡도 : O(n)