219. Contains Duplicate II (중복 포함 II) C#

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

 

정수 배열 nums과 정수 k 주어졌을 때, nums[i] == nums[j]이고 abs(i - j) <= k와 같은 두 개의 고유 인덱스 i와 j가 배열에 존재하면 true를 반환합니다.

 

예시 1:

입력: nums = [1,2,3,1], k = 3
출력: true

예시 2:

입력: nums = [1,0,1,1], k = 1
출력: true

예시 3:

입력: nums = [1,2,3,1,2,3], k = 2
출력: false

조건:

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i]영문 소문자만 포함합니다.

정답:

public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        HashSet<int> hashSet = new HashSet<int>();

        for (int i = 0; i < nums.Length; i++) 
        {
            if (i > k) 
            {
                hashSet.Remove(nums[i - k - 1]);
            }
            if (!hashSet.Add(nums[i])) 
            {
                return true;
            }
        }
 
       return false;
    }
}

해설: 첫번째 풀이에선 단순하게 이중for문으로 풀어보았지만 Time Limit가 떠서 for문을 한번만 사용해서 nums를 한번만 돌자고 생각했습니다.

그래서 두번째 풀이에선 for문을 한번만 사용하고 nums[0]을 삭제한 후 memory에 기억한 후 그 값을 FindIndex를 이용해서 찾아 풀도록하였지만 이 코드 또한 결국 2중 for문처럼 두번 탐색하여 Time Limit가 떴습니다.

마지막 세번째 풀이에선 HashSet을 이용하여 nums[i] 값을 Add해 주지만 k보다 i가 클 경우 삭제하게하여 k의 크기만큼만 HashSet에 기억하게하여 풀었습니다.