[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};
        
    }
}