-
leetcode top interview 150 | Contains Duplicate II | HashMapPS 2023. 9. 1. 08:31
Question
서로 다른 인덱스 i, j의 값이 같고(nums[i] == nums[j])
인덱스 길이의 차이가 k보다 작거나 같을 경우(abs(i-j) <= k) true, 아닐 경우 false 리턴
Accepted Code
class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); boolean result = false; for(int i=0; i<nums.length; i++){ if(!map.containsKey(nums[i])){ map.put(nums[i], i); }else{ int idx = map.get(nums[i]); if(i - idx <= k) result = true; map.put(nums[i], i); } } return result; } }
Solve
nums의 값이 distinct하지 않을 경우 이전에 저장된 index를 꺼내 현재 index와의 차이를 비교하여 boolean 결과값을 저장하는 것으로 생각했다.
따라서 key의 중복을 허용하지 않는 HashMap 구조를 활용하여 key에 nums 값을 넣고 value에 index 값을 넣어 저장했다.
constainsKey로 중복된 key가 있는지 확인할 수 있기 때문에, 중복 키일 시 abs(i-j)값을 확인 하고 hashmap의 value를 최근의 index값으로 갱신해줘 다음 중복 발생 시 비교할 수 있게 처리했다.
'PS' 카테고리의 다른 글