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刷题。
本文分享自微信公众号 - 专知(Quan_Zhuanzhi),作者:关关
原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。
原始发表时间:2017-09-28
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句