Sunday, July 5, 2015

LeetCode [219] Contains Duplicate II

 219. Contains Duplicate II

Easy

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 absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for(int i=0; i<(int)nums.size(); ++i){
            int v = nums[i];
            if(hash.count(v)>0){
                if(i-hash[v]<=k) return true;
            }
            hash[v] = i;
        }
        return false;
    }
};
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        set<int> s;
        for(int i=0; i<(int)nums.size(); ++i){
            if(i>k){
                s.erase(nums[i-k-1]);
            }
            if(s.count(nums[i])) return true;
            s.insert(nums[i]);
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        int l = nums.length;
        for(int i=0; i<l; ++i)
        {
            if(set.contains(nums[i])) return true;
            set.add(nums[i]);
            if(set.size()>k){
                set.remove(nums[i-k]);
            }
        }
        return false;
    }
}

No comments:

Post a Comment