关关的刷题日记05 —— Leetcode 219. Contains Duplicate II

关小刷刷题06 – Leetcode 219. 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.

方法

和217. Contains Duplicate 的区别是这个题目要求i和j的距离不能超过k.那么217中的方法1就没法用了，可以采用方法2的思路，不同的是需要用哈希表来标记，value存对应元素的下标，用来判断距离是否不超过k. 时间复杂度O(n).

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

活到老，学到老，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang），并注明加到Leetcode刷题。
同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。