首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 219: 存在重复元素 II Contains Duplicate II

LeetCode 219: 存在重复元素 II Contains Duplicate II

作者头像
爱写bug
发布2019-11-10 17:29:21
3080
发布2019-11-10 17:29:21
举报
文章被收录于专栏:爱写Bug爱写Bug

题目:

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

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.

示例 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 的滑动窗口,该窗口遍历到的第 i 个元素,后 K 个元素组成的数组 nums[ i, i + K] , 查找该数组内是否有与 nums [i] 相等的元素

可以优化的地方只有维护的滑动窗口这一部分,降低在这个动态数组中查找操作的时间复杂度

优化一个数组内的查找时间复杂度的方法非常多:

  • 暴力破解:直接操作指针将正在遍历的元素与其之后 K 个元素的值对比
  • 平衡二叉树:构建一个平衡二叉树维护这个滑动窗口
  • 哈希集合:维护一个长度为 K 的哈希集合,查找复杂度为 O (1)

秦策只有用哈希集合维护滑动窗口才不会超时

HashSet 解题:

Java:

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])) return true;
            set.add(nums[i]);
            if(set.size()>k) set.remove(nums[i - k]);
        }
        return false;
    }
}

Python:

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hash_set = set()
        for i, num in enumerate(nums):
            if num in hash_set: return True
            hash_set.add(num)
            if (len(hash_set) > k): hash_set.remove(nums[i - k])
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-11-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爱写Bug 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目:
  • 解题思路:
  • HashSet 解题:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档