专栏首页编程理解Leetcode 219. 存在重复元素 II

Leetcode 219. 存在重复元素 II

题目描述

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3

输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1

输出: true

示例 3:

输入: nums = [1,2,3,1,2,3], k = 2

输出: false

题意为,若在 k+1 个长度的子数组中存在两个元素相同,则返回 true,否则返回 false。

解法

以滑动窗口形式来判断窗口覆盖范围内是否存在两个元素相等。因为要判断元素是否存在,所以这里使用 set 集合作为窗口覆盖元素的存储结构。

若使用数组作为存储结构,当 k 较大时,可能会存在计算超时情况。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if k==0:
            return False
        s=set()
        for i in range(len(nums)):
            if nums[i] in s:
                return True
            if i-k>=0:
                s.remove(nums[i-k])
            s.add(nums[i])
        return False

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如果,程序猿都集体消失了...

    腾讯NEXT学位
  • 手把手教你打造 SDN 网路(四) (设定外部联网)

    首先按下 Ctrl+D 登出 root 跟 Ubuntu 回到 Host 之后用 vagrant 指令关掉并且杀掉 VM

    腾讯云TStack
  • 小甲师兄谈谈 Ceph中的不均衡性

    目前OpenStack后端存储广泛使用Ceph,而且一般使用的都是三副本,以空间换可靠性来保证存储数据的安全,由于数据冗余,真实可用容量最多也只能达到集群的1/...

    腾讯云TStack
  • 想进大厂光靠背面试题可没用,谈谈如何真正掌握一个技术知识点

    如何真正地掌握一个技术知识点,这是我一直在探索的一个问题,在秋招复习的那段时间,我主要通过阅读博客、整理博客等方式构建了自己的知识体系,所以也算是有了一些经验,...

    乔戈里
  • 干货 | 小程序自定义组件知多少

    基于小程序的双线程设计,视图层(Webview 线程)和逻辑层(JS 线程)之间通信(表现为 setData),是基于虚拟 DOM 来实现数据通信和模版更新的。

    腾讯NEXT学位
  • 【三分钟】买卖股票的最佳时机 II 的另类解法

    在之前有关 动态规划与股票问题一文 中,小吴使用了动态规划的思想进行了分析和写套路代码,但还是有一些小伙伴不是很明白,今天重新拿出一题从另外一个角度进行分析,希...

    五分钟学算法
  • 让你的双眸焕发神采-亮眼算法解析

        亮眼的效果能够扫去用户面容的疲惫与倦意,是对眼睛进行重塑与编辑的一个重要维度,本文讨论了美容算法中亮眼的一种实现方式。

    天天P图攻城狮
  • 论文中的准确率指标靠谱吗?5个机器学习悖论改变你对数据的看法

    道路越多越拥堵、越智能的算法需要的计算力越少。这些反常识的机器学习悖论你知道是怎么回事吗?

    量子位
  • 记住:永远不要在 MySQL 中使用 UTF-8

    最近我遇到了一个bug,我试着通过Rails在以“utf8”编码的MariaDB中保存一个UTF-8字符串,然后出现了一个离奇的错误:

    良月柒
  • 【Leetcode】124. 二叉树中的最大路径和

    本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

    Leetcode名企之路

扫码关注云+社区

领取腾讯云代金券