【LeetCode-Algorithms】219. Contai

题目

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.

题目大意

给定整数数组和整数k，找出数组中是否有两个不同的索引i和j，使得nums [i] = nums [j]，i和j之间的绝对差值最多为k。

解题思路

这个题是上一个题的升级版，只需要在相等的时候做一下判断即可。
但需要注意的是，如果一个数同时出现多次，当临近两次不匹配的时候，需要将值对应的下标更新，否则会出现一直不匹配的情况。

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