Java HashSet solutions.


  • 0
    G

    public class Solution {

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

    }


  • 0
    S

    this has O(n2) complexity. try to use the hashset to check if the new element exists in i-k previous elements. For this you would need to remove the i-kth element from the set. Use this technique instead of the inner for loop to get O(n) complexity.


  • 0
    J

    why {1,2,1} return false?I always dont understand


Log in to reply
 

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