文档章节

LeetCode:Contains Duplicate II - 判断数组内是否有重复元素2

北风其凉
 北风其凉
发布于 2015/10/15 13:52
字数 628
阅读 2846
收藏 0
点赞 0
评论 0

1、题目名称

Contains Duplicate II(判断数组内是否有重复元素2)

2、题目地址

https://leetcode.com/problems/contains-duplicate-ii/

3、题目内容

英文: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 difference between i and j is at most k.

中文:给出一个整数数组,判断该数组内是否有两个元素值是相同的,且他们的索引值相差不大于k,是则返回true,否则返回false

4、一个TLE的方法

本题如果直接使用暴力方法解决会运行超时。一段TLE的Java代码如下:

/**
 * @功能说明:LeetCode 219 - Contains Duplicate II
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月15日
 */
public class Solution {
    
    /**
     * 查看数组内是否有重复元素且相邻重复元素索引间隔不大于K
     * @param nums
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        
        if (nums.length <= 1) {
            return false;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= i + k && j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

5、解题方法1

一个比较容易想到的方式是使用HashMap来完成目标,使用HashMap解决本题的方式与解决第217题的方式(Contains Duplicate)非常类似。

Java代码如下:

import java.util.HashMap;

/**
 * @功能说明:LeetCode 219 - Contains Duplicate II
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月15日
 */
public class Solution {
    
    /**
     * 查看数组内是否有重复元素且相邻重复元素索引间隔不大于K
     * @param nums
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        
        if (nums.length <= 1) {
            return false;
        }

        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i]) && i - hashMap.get(nums[i]) <= k) {
                return true;
            }
            hashMap.put(nums[i], i);
        }
        
        return false;
    }
}

6、解题方法2

另一种方式是使用HashSet来解决本问题。HashSet是使用HashMap实现的集合。在HashSet的add函数中,如果被插入的元素已存在,则返回true,否则返回false。下面的Java代码就是利用了HashSet的这个性质:

import java.util.HashSet;

/**
 * @功能说明:LeetCode 219 - Contains Duplicate II
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月15日
 */
public class Solution {

    /**
     * 查看数组内是否有重复元素且相邻重复元素索引间隔不大于K
     * 
     * @param nums
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        if (nums.length <= 1) {
            return false;
        }

        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                hashSet.remove(nums[i - k - 1]);
            }
            if (!hashSet.add(nums[i])) {
                return true;
            }
        }

        return false;
    }
}

END

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 114
博文 497
码字总数 462457
作品 4
朝阳
程序员
LeetCode:Contains Duplicate - 判断数组内是否有重复元素

1、题目名称 Contains Duplicate(判断数组内是否有重复元素) 2、题目地址 https://leetcode.com/problems/contains-duplicate/ 3、题目内容 英文:Given an array of integers, find if t...

北风其凉
2015/10/13
947
0
Leetcode日记6

(2015/11/28) LeetCode 303 Range Sum Query - Immutable:(Easy) 1)超时的算法:每次调用sumRange函数进行一次累加运算。 2)不超时的算法:改变数组的内容,存储从0下标到当前下标所有...

fxdhdu
2015/11/28
73
0
287. Find the Duplicate Number。

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only o......

Leafage_M
01/26
0
0
玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set和map 容器类 屏蔽实现细节 了解语...

天涯明月笙
2017/09/21
0
0
leetcode题解(查找表问题)

查找,是使用计算机处理问题时的一个最基本的任务,因此也是面试中非常常见的一类问题。很多算法问题的本质,就是要能够高效查找。学会使用系统库中的map和set,就已经成功了一半。 set的使用...

吴小琪
06/21
0
0
Leetcode日记8

(2015/2/3) LeetCode 4 Median of Two Sorted Arrays 题目大意:找到两个已排序数组的median。 median:中间位置的值。 算法: 参考:https://leetcode.com/discuss/15790/share-my-o-log...

fxdhdu
2016/02/18
94
0
面试精选之位操作问题集锦

Java 中位运算符有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>),只针对 int 类型有效,也可以作用于 byte、short、char、long,当为这四种类型时,J...

JohnnyShieh
2017/12/28
0
0
LeetCode Contains Duplicate

LeetCode Contains Duplicate Mz的博客2016-03-15173 阅读 算法C/C++ Contains Duplicate 原题传送门: https://leetcode.com/problems/contains-duplicate/ Contains Duplicate II 原题传送门......

Mz的博客
2016/03/15
0
0
[leetcode]Array

写在前面:解决数组问题有一些常见的思路,下面,在这里,对相应问题进行汇总。 一.定义新的索引 283 remove zeros(将数组中的零元素移到末尾) Given an array , write a function to mov...

u013250416
2017/11/13
0
0
[算法][LeetCode] 数组

[算法][LeetCode]Search a 2D Matrix——二维数组的二分查找 http://www.cnblogs.com/hiddenfox/p/3402797.html 将排序的二维数组看做一维数组来处理。不重构数据的情况下,将二分查找的一维...

素雷
2017/10/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

springboot常用注解

@SpringBootApplication: 包含@Configuration、@EnableAutoConfiguration、@ComponentScan 通常用在主类上。 @Service: 用于标注业务层组件。 @RestController: 用于标注控制层组件(如strut...

GoldenVein
9分钟前
0
0
梯度下降法求多元线性回归及Java实现

对于数据分析而言,我们总是极力找数学模型来描述数据发生的规律, 有的数据我们在二维空间就可以描述,有的数据则需要映射到更高维的空间。数据表现出来的分布可能是完全离散的,也可能是聚...

冷血狂魔
14分钟前
2
0
如何进行大数据的入门级学习?

不知道你是计算机专业应届生还是已经从业者。总之,有java基础的学生学习大数据会轻松很多,零基础的小白都需要从java和linux学起。 如果你是一个学习能力特别强,而且自律性也很强的人的话可...

董黎明
23分钟前
0
0
使用Parcelable传递复杂参数

最近做AIDL传递对象,对象必须实现Parcelable的方法才可以被传递。 @Override    public int describeContents() {//这个 默认返回0就行了。        return 0;    }    ...

火云
24分钟前
0
0
十大Intellij IDEA快捷键

Intellij IDEA中有很多快捷键让人爱不释手,stackoverflow上也有一些有趣的讨论。每个人都有自己的最爱,想排出个理想的榜单还真是困难。以前也整理过Intellij的快捷键,这次就按照我日常开发...

HJCui
34分钟前
0
0
word 使用mathtype 编写 数学公式

下载安装,这个链接命名。。。。 http://www.mathtype.cn/xiazai.html 安装之后会多出一个选项 使用内联方式插入图表 编写公式的界面 设置支持latex 语法 输入公式回车就可以看到结果...

阿豪boy
52分钟前
0
0
Promise

定义 Promise是异步编程的一种解决方案,所谓Promise就是一个容器,里面保存着某个未来才会结束的事件(通常是一个一步操作)的结果。 特点: 2.1 对象的状态不受外界影响,三种状态pending...

litCabbage
今天
1
0
设计模式:适配器模式

说明:在不改变旧接口代码的前提下,为该接口新增其他接口的功能 适配器模式可以分为:类适配器模式、对象适配器模式、接口适配器模式 前两种模式下,我会以播放器为例。老版的播放器(Playe...

人觉非常君
今天
0
0
使用VsCode搭建Java开发环境,创建springboot应用

1、在 Visual Studio Code 中打开扩展视图(Ctrl+Shift+X),输入关键词java、spring分别下载Java开发插件包和springboot插件包 2、配置参数 点击设置按钮,进入设置选项,配置用户设置 在用户...

qsyan
今天
24
0
调教属于你的“贾维斯”(给自己挖了一个很大的坑)

今天玩一下现在很火的人工智能。 废话不多说,先来看几张图: 看出什么蹊跷了吗? 再来看一个视频: https://www.zhihu.com/video/1002567561061511168 (演示网址和代码见文末) 人工智能离...

crossin
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部