Java solution using Set and sliding window


  • 16
    W

    My solution is simple. My set only contain the numbers in the window. slide the window which is size k, if the new coming number cannot be add to set then return true. The time complexity is O(n), space complexity is O(k).

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

  • 3
    L

    Here is my code with the same idea, which is more simpler:

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.