关关的刷题日记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刷题。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-09-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3

关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3 方法2 方法2:遍历数组,遇到...

2559
来自专栏专知

关关的刷题日记85 – Leetcode 326. Power of Three

关关的刷题日记85 – Leetcode 326. Power of Three 题目 Given an integer, write a function t...

37410
来自专栏专知

关关的刷题日记10——Leetcode 1. Two Sum 方法1

关小刷刷题10 – Leetcode 1. Two Sum 方法1 题目 Given an array of integers, return indices ...

3089
来自专栏专知

关关的刷题日记96 – Leetcode 120. Triangle

关关的刷题日记96 – Leetcode 120. Triangle 题目 Given a triangle, find the minimum path su...

3485
来自专栏大数据钻研

JavaScript 世界万物诞生记

一. 无中生有 起初,什么都没有。 造物主说:没有东西本身也是一种东西啊,于是就有了null: ? 现在我们要造点儿东西出来。但是没有原料怎么办? 有一个声音说...

3458
来自专栏专知

【LeetCode 136】 关关的刷题日记32 Single Number

关关的刷题日记32 – Leetcode 136. Single Number 题目 Given an array of integers, every ele...

3516
来自专栏数据结构与算法

1074 食物链 2001年NOI全国竞赛

1074 食物链 2001年NOI全国竞赛 时间限制: 3 s 空间限制: 64000 KB 题目等级 : 钻石 Diamond 题目描述 Des...

3556
来自专栏专知

关关的刷题日记81 – Leetcode 258. Add Digits

关关的刷题日记81 – Leetcode 258. Add Digits 题目 Given a non-negative integer num, repeat...

2787
来自专栏专知

【LeetCode 136】 关关的刷题日记33 Intersection of Two

关关的刷题日记33 – Leetcode 349. Intersection of Two Arrays 题目 Given two arrays, write ...

2975
来自专栏数据结构与算法

P1372 又是毕业季I

题目背景 “叮铃铃铃”,随着高考最后一科结考铃声的敲响,三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍,憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑...

3244

扫码关注云+社区

领取腾讯云代金券