[LeetCode] 219. Contains Duplicate II

orca·2023년 8월 31일
0

problem

목록 보기
21/28

https://leetcode.com/problems/contains-duplicate-ii/

개요

  1. 정수 배열 nums[] 와 정수 k가 주어진다.
  2. 간격 k 이내에 중복된 정수가 있는지 확인해라.
    • abs(i - j) <= k

문제 해결 아이디어

  • 어떤 숫자가 특정 인덱스 범위 내에 있는지 확인해야 한다.

🤨 자료구조 Map을 이용하자

➡️ map을 이용해 (숫자-인덱스) 쌍을 저장하자

의사 코드

  1. 배열을 순차적으로 검사한다.
  2. nums[i] 가 map에 존재하고, i - j <= k 이다. (조건)
    2-1. true를 리턴함
  3. map에 nums[i]를 키로 인덱스를 value로 저장한다.
for(int i=0, 배열 끝까지){
	if(map.get(nums[i]) >= i - k){
    	return true
    }
    map.put(nums[i],i)
}
return false

결과

전체 코드 github 링크

다른 풀이

public boolean containsNearbyDuplicate(int[] nums, int k) {
      HashMap<Integer, Integer> cache = new HashMap<>();
      int length = nums.length;
      for (int i = 0; i < length; i++) {
        Integer prev = cache.put(nums[i], i);
        if (prev != null && i - prev <= k) {
          return true;
        }
      }
    return false;
  }

나와 동일하게 문제를 풀이한 것 같다.
그런데 Map에 이미 있는 key는 이전 value를 반환한다는 것을 새롭게 배웠다.

0개의 댓글