[LeetCode/Top Interview 150] [Hash Table] 219. Contains Duplicate II

문제 링크: https://leetcode.com/problems/contains-duplicate-ii/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

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.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

전략:

최대 K 만큼 떨어진 범위 안에 존재하는 서로 다른
두 요소가 중복인 경우가 존재하는지 체크하고 리턴
슬라이딩 윈도우 + HashSet으로 해결 가능할듯

코드 구현:

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k==0) return false;
        HashSet<Integer> set = new HashSet<Integer>();        
        for (int i=0;i<Math.min(k,nums.length);i++) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
        }

        for (int i=0;i<nums.length-k;i++) {
            if (set.contains(nums[i+k])) return true;
            set.remove(nums[i]);
            set.add(nums[i+k]);
        }
        return false;
    }
}
Time: 19 ms (61.35%), Space: 54.4 MB (92.75%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0219-contains-duplicate-ii/0219-contains-duplicate-ii.java

개선 방안:

set.contains(nums[i+k]) 대신 !set.add(nums[i+k]) 로 중복여부 체크와 삽입을 동시에 진행

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k==0) return false;
        HashSet<Integer> set = new HashSet<Integer>();        
        for (int i=0;i<Math.min(k,nums.length);i++) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
        }

        for (int i=0;i<nums.length-k;i++) {
            if (!set.add(nums[i+k])) return true;
            set.remove(nums[i]);
        }
        return false;
    }
}
Time: 17 ms (86.25%), Space: 54.64MB (90.90%) - LeetHub

Solutions 탭의 타인 코드:

public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(i > k) set.remove(nums[i-k-1]);
            //remove element if its distance to nums[i] is not lesser than k
            // set에 저장된 요소 중 현재 nums[i]와 k를 초과한 거리만큼 떨어져있는 요소를 삭제
            if(!set.add(nums[i])) return true;
            //because all still existed elements is closer than k distance to the num[i],
            //therefore if the add() return false, it means there's a same value element
            //already existed within the distance k, therefore return true.
            // set에 아직까지 남아있는 요소들은 모두 nums[i]와 k이하의 거리를 가지므로,
            // set에 nums[i]를 추가하지 못한 경우 = 이미 존재하는 경우이므로 true 리턴
        }
        return false;
 }
 Time: 13 ms (99.41%), Space: 56.8 MB (48.96%) - LeetHub

회고:

엣지케이스에 대한 생각을 좀 더 많이 해서 실제 제출 전에 걸러내는 연습이 더 필요할 듯 하다.