[Dart] 219. Contains Duplicate II

 

1. 문제

https://leetcode.com/problems/contains-duplicate-ii/?envType=study-plan-v2&envId=top-interview-150

 

 

2. 요구 사항

1) 정수 배열 nums와 정수 k가 주어진다.

2) nums에는 서로 다른 i, j 인덱스가 있고, abs(i - j) <= k 를 만족하면 true를 반환한다.

3) 조건에 맞지 않을 경우에는 false를 반환한다.

 

 

 

3. 핵심 아이디어

1) 슬라이딩 윈도우 + Set

 

슬라이딩 윈도우는 최근 k개의 값만 저장하는 것이 목표이다.

 

nums 배열을 순회하면서, 최근 k개 이내의 값을 Set에 저장한다.

 

Set는 중복을 허용하지 않기 때문에, 값이 이미 들어있으면 중복이라는 뜻이다.

k거리 이내에서 중복이 발생한 것이기 때문에 이는 요구사항에 부합한다.

 

만약, Set의 크기가 k개를 넘어가면 가장 오래된 값을 제거한다.

 

 

2) 코드

class Solution {
  bool containsNearbyDuplicate(List<int> nums, int k) {
  	// 중복된 값이 k 거리 이내에 있는지 확인
    Set<int> window = {};		// 최근 k개의 값을 저장할 Set

	// 현재 값이 window에 이미 있다면, k 거리 이내에서 중복이 발생한 것
    for (int i = 0; i < nums.length; i++) {
        if (window.contains(nums[i])) {
            return true;
        }

		// 현재 값을 window에 추가
        window.add(nums[i]);

		// 윈도우 크기가 k를 초과하면 가장 오래된 값 제거
  		// 이렇게 하면 항상 최근 k개의 값만 유지됨
        if (window.length > k) {
            window.remove(nums[i - k]);
        }
    }

	// 끝까지 중복이 없으면 false 반환
    return false;
    }
}

 

- 시간 복잡도 : O(n)

- 공간 복잡도 : O(k)

 

3) Map

nums의 값과 최근 인덱스를 저장하기 위해 Map을 사용한다.

 

nums배열을 순회하면서 같은 숫자가 등장했을 때,

저장된 인덱스와 현재 인덱스의 차이가 k 이하인 경우 true를 반환한다.

 

그렇지 않으면 현재 숫자와 인덱스를 Map에 추가한다.

 

4) 코드

bool containsNearbyDuplicate(List<int> nums, int k) {
  // nums의 값과 최근 등장 인덱스를 저장
  Map<int, int> indexMap = {};

  for (int i = 0; i < nums.length; i++) {
    // 만약 숫자가 Map에 존재하고 인덱스 차이가 k 이하라면 true 반환
    if (indexMap.containsKey(nums[i]) && (i - indexMap[nums[i]]!) <= k) {
      return true;
    }
    // 현재 숫자와 인덱스를 Map에 업데이트
    indexMap[nums[i]] = i;
  }

  // 조건을 만족하는 경우가 없으면 false 반환
  return false;
}

 

- 시간 복잡도 : O(n)

- 공간 복잡도 : O(n)