Contains Duplicate II问题及解法

本文主要是介绍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 absolute difference between i and j is at most k.

问题分析：

找到数组中相同的两个元素之间索引值之差最大为k，可利用map来求解。

1.若nums[i]在map中不存在，将<nums[i],i>存入map；

2.若已存在，看当前索引值与map中存的之差是否小于等于k，若满足，则返回true；若不满足，更改map中nums[i]对应的索引值;

3.重复1,2，直到最后

过程详见代码：

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {map<int,int> m;for(int i = 0; i < nums.size(); i++){if(m.count(nums[i]) == 0){m.insert(pair<int,int>(nums[i],i));}else if(i - m[nums[i]] <= k){return true;}else m[nums[i]] = i;}return false;}
};

这篇关于Contains Duplicate II问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---