Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

My solution (solution 1) is the most elementary method to deal with problem like this, but it has O(n^2) complexity.

/*Solution 1*/
public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null) {
            return false;
        }

        for (int i = 0; i < nums.length - 1 - k; i++) {
            for (int j = 1; j <= k; j++) {
                if (i+j > nums.length) {
                    continue;
                }

                if (nums[i] == nums[i+j]) {
                    return true;
                }
            }
        }
        return false;
}

I searched the answer for this problem, and I found solution 2.
This solution uses HashMap and thus decrease the time
complexity to O(1). Some important methods of HashMap class are:
* boolean containKey(Object key)
* boolean containValue(Object value)
* boolean isEmpty()
* V put (K key, V value)
* remove (Object key)
* int size

public boolean containsNearbyDuplicate(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    //Key: nums[i]
    //value: i
    for(int i=0; i++; nums.length; i++){
        if(map.containsKey(nums[i])){
            int pre = map.get(nums[i]);
            if(i-pre<=k)
                return true;
            }
            map.put(nums[i], i);
        }
    return false;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s