专栏首页专知关关的刷题日记05 —— Leetcode 219. Contains Duplicate II

关关的刷题日记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),作者:关关

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2

    题目 Leetcode 217. Contains Duplicate Given an array of integers, find if the arra...

    WZEARW
  • 【专知-关关的刷题日记15】Leetcode 27. Remove Element 方法1、2、3

    题目 Given an array and a value, remove all instances of that value in place and r...

    WZEARW
  • 关关的刷题日记09——Leetcode 80. Remove Duplicates from Sorted Array II

    关小刷刷题09 – Leetcode 80. Remove Duplicates from Sorted Array II 方法1、2 题目 Follow up...

    WZEARW
  • 将有序数组转化为二叉搜索树

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    你的益达
  • LeetCode 80. 删除排序数组中的重复项 II

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

    Michael阿明
  • Leetcode 27. Remove Element

    Tyan
  • 【leetcode刷题】20T16-移除元素

    https://leetcode-cn.com/problems/remove-element/

    木又AI帮
  • 2020-11-07:已知一个正整数数组,两个数相加等于N并且一定存在...

    2020-11-07:已知一个正整数数组,两个数相加等于N并且一定存在,如何找到两个数相乘最小的两个数?

    福大大架构师每日一题
  • 算法篇:二分法之k个数之和

    这类题目是二分法的典型题目,核心点就是实现二数之和,三数之和,四数之和,多数之和都属于这类题目的变形题目。本文章统一整理了一个套路,多数之后最终转化为二数之和,...

    灰子学技术
  • LeetCode|560. 和为K的子数组--C++题解

    本题原本按我最喜欢的暴力破解提交的,结果到最后几个大数据的时候提示超时了,最后也是看了官方的思路,了解了动态规划的思路去解的这个题,所以本篇写了两个实现的方法。...

    Vaccae

扫码关注云+社区

领取腾讯云代金券