3ms Java Solution


  • 1
    Y
    public boolean containsDuplicate(int[] nums) {
    	if (nums == null) {
    		return false;
    	}
    	int[] hashTable = new int[nums.length];
    	for (int i = 0; i < hashTable.length; i++) {
    		hashTable[i] = Integer.MIN_VALUE;
    	}
    	for (int i = 0; i < nums.length; i++) {
    		int h = nums[i] % nums.length;
    		h = h >= 0 ? h : h + nums.length;
    		while (hashTable[h] != Integer.MIN_VALUE) {
    			if (nums[i] == hashTable[h]) {
    				return true;
    			} else {
    				h = (h + 1) % nums.length;
    			}
    		}
    		hashTable[h] = nums[i];
    	}
    	return false;
    }

  • 0
    A

    Very innovative, but nums = [MIN_VALUE, MIN_VALUE] will return false.
    A quick fix is to add a boolean inUse array to replace MIN_VALUE as the residency test.


  • 0
    H
    This post is deleted!

  • 1
    A
    public boolean containsDuplicate(int[] nums) {
        if (nums == null) {
            return false;
        }
        int[] hashTable = new int[nums.length];
        // Separate residency array to avoid problems with Integer.MIN_VALUE in the input array.twice
        boolean[] occupied = new boolean[nums.length];
        for (int i = 0; i < hashTable.length; i++) {
            occupied[i] = false;
        }
        for (int i = 0; i < nums.length; i++) {
            int h = nums[i] % nums.length;
            h = h >= 0 ? h : h + nums.length;
            while (occupied[h]) {
                if (nums[i] == hashTable[h]) {
                    return true;
                } else {
                    h = (h + 1) % nums.length;
                }
            }
            hashTable[h] = nums[i];
            occupied[h] = true;
        }
        return false;
    }

Log in to reply
 

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