Simple Java solution


  • 253
    S
    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]);
                if(!set.add(nums[i])) return true;
            }
            return false;
     }

  • 0
    L

    Good , set doesn't avoid dul;


  • 0
    T

    Could this be explain in laymen's terms?
    edit: I understand the logic now, all good


  • 0
    C

    Great. This runs much more efficiently than with HashMap.


  • 47
    S

    Explanation: It iterates over the array using a sliding window. The front of the window is at i, the rear of the window is k steps back. The elements within that window are maintained using a set. While adding new element to the set, if add() returns false, it means the element already exists in the set. At that point, we return true. If the control reaches out of for loop, it means that inner return true never executed, meaning no such duplicate element was found.


  • 3
    This post is deleted!

  • 0
    N

    HashSet: "It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. "
    So can we still count on the index of HashSet?


  • 0

    sliding windows based solution ! really nice


  • 1
    A

    we are storing at most k elements in hash set at one time. so not hashset, but the sliding window logic is more space efficient then plain hash map method. Running time complexity is similar anyways.


  • 0
    S

    hi, maybe we could try TreeSet.


  • 0
    A

    why when I run this code, I got " Time Limit Exceeded "?
    But no such problem by HashMap solution.


  • 1
    S

    Leetcode should consider some of the time exceed failures. I wrote a code with O(n) and failed at the first time, then I repeated the same one and succeeded. It' s apparent the running time is influenced by some other factors.
    I don't think it's really neccesary to put hard restriction on the time limit. As long as you're running O(n) time, you should be fine. In real life, you also need to consider the code to be readable which sometimes can be a tradeoff of performance.


  • 0
    D

    You got a point. But how leetcode be able to detect your algorithm is o(n)? Simply by analyzing the loop?


  • 0
    S

    When I changed the statement of "for" loop, why the runtime error happened?

    public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set=new HashSet<Integer>();
    for(int num:nums){
    if(num>k) set.remove(nums[num-k-1]);
    if(!set.add(nums[num])) return true;
    }
    return false;
    }


  • 0
    S

    @Shellen because you are manipulating the number, and not it's position. i.e. if nums[4] = 10;
    you are manipulating the value (10) and not it's position (4). Hope you understood.


  • 0
    W
    This post is deleted!

  • 0
    C

    Hey, I have a question. At first, I declare the set to be HashSet set = new HashSet();
    and finally I got TLE, can somebody tell me why?

    I went to the stack overflow, they all recommend we should code like:
    Set set = new HashSet();
    Because if you decide not to use hashset anymore, you can change to another inherited class just by one line. But still I don't know why it will be more slower if I declare set to be HashSet.


  • 1
    S

    @RECUrison I don't think it is Set's problem that made you get TLE. Actually Set is just an interface so that Set<Integer> set = new HashSet<>() actually uses HashSet. I tried to submit the solution in both Set and HashSet multiple times and there was no apparent difference in performance between them. So I think there may be something can be improved in your code. I didn't see your code, but there is the thing you should notice: since set.add() returns a boolean type, it would get a slight performance improvement avoid using set.contains().


  • 0
    K

    @RECUrison Same question with you. I used HashMap and TLE but when I changed it to Map it was accepted


  • 0
    L

    Ran this code, but failed


Log in to reply
 

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