LeetCode 1: HashMap으로 Two Sum의 두 인덱스 찾기
필요한 나머지 값을 찾습니다
배열 nums에서 합이 target이 되는 두 원소의 인덱스를 반환하는 문제입니다. 같은 원소를 두 번 사용할 수는 없습니다.
현재 값이 nums[i]이면 함께 필요한 값은 target - nums[i]입니다. 앞서 본 값을 키로, 그 인덱스를 값으로 저장하는 해시맵을 사용했습니다.
먼저 필요한 값이 맵에 있는지 확인해서 있으면 저장된 인덱스와 현재 인덱스를 반환합니다. 없으면 현재 값과 인덱스를 맵에 넣고 다음 원소를 봅니다. 조회한 다음 저장하므로 현재 원소를 자기 자신과 짝짓지 않습니다.
배열은 한 번만 순회합니다. 해시맵의 조회와 저장을 평균 O(1)로 볼 때 전체 시간은 평균 O(N)입니다.
코드
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hmap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (hmap.containsKey(target - nums[i])){
return new int[] {hmap.get(target - nums[i]), i};
}
hmap.put(nums[i], i);
}
return new int[] {};
}
}