Leetcode: Contains Duplicate II

Datetime:2016-08-23 01:20:56          Topic: LeetCode           Share

Question

Contains Duplicate IIGiven 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.

Analyze

It’s strait forward to using dictionary on this question. First run, save position of each number in the dictionary; Second run, check the dictionary to see if there is another duplication in this array and check the position of it.But there is a situation that need take into consideration, that the array may contain the duplication multiple times. To deal with this, just checking in the first run, to see if the last position (if any) is close enough.

Code

C++ code

class Solution {
public:
    inline int abs(int v) {
        return v < 0 ? -v : v;
    }
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> dict;
        for(int i=0; i<nums.size(); ++i) {
            if(dict.find(nums[i]) != dict.end()) {
                if(abs(dict[nums[i]]-i) <= k)
                    return true;
            }
            dict[nums[i]]=i;
        }
        for(int j=0; j<nums.size(); ++j){
            map<int,int>::iterator it = dict.find(nums[j]);
            map<int,int>::iterator endit = dict.end();
            if(endit != it){
                int i = it->second;
                if(i != j && abs(i-j) <= k)
                    return true;
            }
        }
        return false;
    }
};




About List