文档章节

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

北风其凉
 北风其凉
发布于 2015/10/15 13:52
字数 628
阅读 3.2K
收藏 0

码上生花,ECharts 作品展示赛正式启动!>>>

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

© 著作权归作者所有

北风其凉

北风其凉

粉丝 124
博文 497
码字总数 462305
作品 4
朝阳
程序员
私信 提问
加载中
请先登录后再评论。
[LeetCode] 217. Contains Duplicate 包含重复元素

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return fa......

osc_flp5mhtj
2018/03/26
4
0
[LeetCode] 219. Contains Duplicate II 包含重复元素 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......

osc_flp5mhtj
2018/03/26
2
0
[LeetCode] 220. Contains Duplicate III 包含重复元素 III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and t......

osc_flp5mhtj
2018/03/26
2
0
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
1.3K
0
Leetcode日记6

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

fxdhdu
2015/11/28
126
1

没有更多内容

加载失败,请刷新页面

加载更多

Synchronized底层实现

https://blog.csdn.net/qq_35190492/article/details/106180781

JaneRoad
今天
18
0
解决okhttp无法重用连接的问题

解决okhttp无法重用连接的问题 最近在一个程序中使用okhttp调用http接口。开始时一切正常,但是测试运行一段时间后,okhttp就会报告recv失败。同时在调用端机器上,netstat显示很多套接字是T...

tommwq
今天
17
0
入坑Linux-day15(使用DHCP动态管理主机地址)

一、动态主机配置协议(DHCP) #DHCP是一种基于UDP协议且仅限于在局域网内部使用的网路协议,主要用于大型的局域网环境或者存在较多移动办公设备的局域网环境中,其主要用途是为局域网内部的...

宁生写你
今天
8
0
js canvas 旋转90度的整数倍

为了避免出现黑框 效果如下 根据不同的方向,设置宽高和画笔位置等 <!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"/> <title>Title</title> <style> .img ......

阿豪boy
今天
22
0
如何生成随机的字母数字字符串? - How to generate a random alpha-numeric string?

问题: I've been looking for a simple Java algorithm to generate a pseudo-random alpha-numeric string. 我一直在寻找一种简单的 Java算法来生成伪随机的字母数字字符串。 In my situat......

技术盛宴
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部