Leetcode: Contains Duplicate II

Datetime:2016-08-23 01:20:56         Topic: LeetCode          Share        Original >>
Here to See The Original Article!!!


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.


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.


C++ code

class Solution {
    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;
        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;


Put your ads here, just $200 per month.