[LeetCode] Two Sum

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.

Example:

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

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

Solution

간단한 해시맵 문제. nums[i]에 해당되는 모든 해시값을 넣고 target – nums[i] 가 해시에 있나없나만 체크해서 리턴해주면 된다. 시간복잡도는 O(N)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for(int i = 0 ; i < nums.length ; i++){
            map.put(nums[i], i);
        }
        
        for(int i = 0 ; i < nums.length ; i++){ int key = target - nums[i]; if(map.containsKey(key)){ int val = map.get(key); if(val == i) continue; if(val > i )    return new int[]{i, val};
                else            return new int[]{val, i};
            }
        }
        
        return new int[]{0,0};
        
    }
}

풀스택 소프트웨어 엔지니어. 이 블로그는 메튜의 미래를 설계하는 공간. 필터링 되지 않은 생각에 대하여. 대용량 분산처리 (주로 데이터, 머신러닝) 웹 서비스 설계와 데이터 시각화, 풀스택 스타트업, 전자음악에 관심이 많습니다.

Translate »