leetcode面试准备:Contains Duplicate I && II

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1 题目

Contains Duplicate I

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 false if every element is distinct.

接口 : public boolean containsDuplicate(int[] nums)

Contains Duplicate II

Given an array of integers and an integer k, find out whether there 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.

接口： public boolean containsNearbyDuplicate(int[] nums, int k)

2 思路

I：判断数组中有无重复元素。用 HashTable 的思想，实现用 HashSet 来做。

复杂度 : Time：O(n)；Space：O(n)

II : 在I的基础上，判断重复的元素相距离的位置是否在 k 范围之内。用 HashTable 的思想，实现用 HashMap 来做，< key , value > = <数组值，下标index>

复杂度 : Time：O(n)；Space：O(n)

注意：如何更新Map的值？考虑一下注意的测试用例 {1,0,1,1},1

3 代码

	public boolean containsDuplicate(int[] nums) {

		int len = nums.length;

		Set<Integer> set = new HashSet<Integer>(len);

		for (int num : nums) {

			if (set.contains(num)) {

				return true;

			} else {

				set.add(num);

			}

		}

		return false;

	}

	public boolean containsNearbyDuplicate(int[] nums, int k) {

		int len = nums.length;

		Map<Integer, Integer> map = new HashMap<Integer, Integer>(len);

		for (int i = 0; i < len; i++) {

			if (map.containsKey(nums[i])) {

				int diff = i - map.get(nums[i]);

				if (diff <= k)

					return true;

			}

			map.put(nums[i], i); // 不管有没有这个num，都要更新Map的值。为了通过这样的测试用例:{1,0,1,1},1

		}

		return false;

	}

4 总结

解题的思想，主要是 HashTable 。想到就比较简单了。

5 参考

leetcode Contains Duplicate I

leetcode Contains Duplicate II

leetcode面试准备:Contains Duplicate I && II的更多相关文章

LeetCode面试常见100题（ TOP 100 Liked Questions）
LeetCode面试常见100题( TOP 100 Liked Questions) 置顶 2018年07月16日 11:25:22 lanyu_01 阅读数 9704更多分类专栏: 面试编程题真题 ...

leetcode面试准备:Reverse Words in a String
leetcode面试准备:Reverse Words in a String 1 题目 Given an input string, reverse the string word by word. ...

leetcode面试准备: Maximal Rectangle
leetcode面试准备: Maximal Rectangle 1 题目 Given a 2D binary matrix filled with 0's and 1's, find the larg ...

leetcode面试准备: Game of Life
leetcode面试准备: Game of Life 1 题目 According to the Wikipedia's article: "The Game of Life, also k ...

leetcode面试准备: Word Pattern
leetcode面试准备: Word Pattern 1 题目 Given a pattern and a string str, find if str follows the same patte ...

leetcode面试准备:Add and Search Word - Data structure design
leetcode面试准备:Add and Search Word - Data structure design 1 题目 Design a data structure that supports ...

leetcode面试准备:Implement Trie (Prefix Tree)
leetcode面试准备:Implement Trie (Prefix Tree) 1 题目 Implement a trie withinsert, search, and startsWith m ...

leetcode面试准备:Triangle
leetcode面试准备:Triangle 1 题目 Given a triangle, find the minimum path sum from top to bottom. Each step ...

leetcode面试准备:Sliding Window Maximum
leetcode面试准备:Sliding Window Maximum 1 题目 Given an array nums, there is a sliding window of size k wh ...

随机推荐

UNIX线程之间的关系
我们在一个线程中经常会创建另外的新线程,如果主线程退出,会不会影响它所创建的新线程呢?下面就来讨论一下. 1. 主线程等待新线程先结束退出,主线程后退出.正常执行. 示例代码: #include & ...

SQL Server 2008 TOP 新用途
/*创建测试表****************/ IF NOT OBJECT_ID('[Demo_Top]') IS NULL DROP TAB ...

android 中在CMD中查看sqlite
今天第一次学习Sqlite,在代码中执行了sql,但是不知道在上面地方才能直观的查看sqlite中的数据,下面是查看资料后的找到的查看方法: 通过上述可以从cmd进入数据库查看原文地址:http:// ...

Sqlserver With as
with t as (select * from emp where depno=10) 总结:可以看做将查询出来的语句块表示为一个临时表 select * from t where empno=xx ...

linux关闭声音
对于CentOS/Redhat/RHEL/Fedora系统,使用root身份执行:echo "alias pcspkr off" >> /etc/modprobe.co ...

[转]:移动端H5页面高清多屏适配方案
原文链接:http://www.tuicool.com/articles/YJviea 背景开发移动端H5页面面对不同分辨率的手机面对不同屏幕尺寸的手机视觉稿在前端开发之前,视觉MM会给我们 ...

10.12_win8风格，把专业书籍当小说看，SQLite
(1)CSS:Metro UI CSS(Metroui) 是一套实现了 Windows 8 的 Metro 风格界面的 CSS 框架..官网.BootMetro . (2)[开源访谈]CecOS作者 ...

WEB开发原则
1.最小权限原则,只允许用户做,而不是"不允许用户做"2.浏览器查看的是服务端代码的执行输出的文本,除非服务器有漏洞,否则浏览者无法查看服务端的ASPX,CS代码 ...

页面mask css
<html> <head> <style type="text/css"> .share_mask { position: fixed; top ...

通过telnet使用smtp协议发送邮件
smtp协议是一个简单的邮件传输协议,利用它我们可以将邮件发送给别人,这里将通过telnet这个程序利用smtp协议从网易向gmail发送一封邮件网上不少有说使用telnet发送邮件的文章,我也看过 ...

正文

1 题目

Contains Duplicate I

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 false if every element is distinct.

Contains Duplicate II

Given an array of integers and an integer k, find out whether there 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.

2 思路

3 代码

I
`public boolean containsDuplicate(int[] nums) { int len = nums.length; Set<Integer> set = new HashSet<Integer>(len); for (int num : nums) { if (set.contains(num)) { return true; } else { set.add(num); } } return false; }`

4 总结

5 参考

leetcode Contains Duplicate I

leetcode Contains Duplicate II

相关阅读

linux主频命令，linux 内存主频

linux翻页命令，linux翻页命令n

宝鸡sap维护公司，宝鸡sap维护公司有哪些

上饶香港服务器大概价格，香港服务器哪个服务商好

两块显卡怎么交火，两个显卡交火可以挖矿吗

鸿蒙系统下载指导，鸿蒙下载方法

日服怎么更新ios，日服更新太慢

hdfs文件导入hbase数据库，hbase是以hdfs为数据存储的数据库

目录[+]

1 题目

Contains Duplicate I 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 false if every element is distinct.

Contains Duplicate II Given an array of integers and an integer k, find out whether there 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.

2 思路

3 代码

I public boolean containsDuplicate(int[] nums) { int len = nums.length; Set<Integer> set = new HashSet<Integer>(len); for (int num : nums) { if (set.contains(num)) { return true; } else { set.add(num); } } return false; }

4 总结

5 参考 leetcode Contains Duplicate I leetcode Contains Duplicate II

相关阅读

linux主频命令，linux 内存主频

linux翻页命令，linux翻页命令n

宝鸡sap维护公司，宝鸡sap维护公司有哪些

上饶香港服务器大概价格，香港服务器哪个服务商好

两块显卡怎么交火，两个显卡交火可以挖矿吗

鸿蒙系统下载指导，鸿蒙下载方法

日服怎么更新ios，日服更新太慢

hdfs文件导入hbase数据库，hbase是以hdfs为数据存储的数据库

目录[+]

Contains Duplicate I

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 false if every element is distinct.

Contains Duplicate II

Given an array of integers and an integer k, find out whether there 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.

I
`public boolean containsDuplicate(int[] nums) { int len = nums.length; Set<Integer> set = new HashSet<Integer>(len); for (int num : nums) { if (set.contains(num)) { return true; } else { set.add(num); } } return false; }`

5 参考

leetcode Contains Duplicate I

leetcode Contains Duplicate II