LeetCode 219.Contains Duplicate II

今天是大年初七,祝大家新年快乐!万事如意!恭喜发财!

同时也是实现今年小目标的第一篇文章:LeetCode 219 题解

说说LeetCode

作为大名鼎鼎的面试刷题网站,最近也出了中文版,如果之前没有了解过的童鞋,建议去网站看看,里面有各大互联网公司的算法面试题,包括谷歌,Fackbook,微软,亚马逊等等,近年来国内的互联网公司也越来越重视算法和数据结构了,特别是后端,经常看到高级工程师 职位以上的jd都写明,算法水平需要到LeetCode Hard程度,前端稍微好一点,但是也需要LeetCode Easy 水平,因此无论是为了巩固基础,还是找工作跳槽,我们都需要不断练习算法,那么比较好的方式自然就是找一个靠谱的平台刷题了。

英文网站:https://leetcode.com/

中文网站:https://leetcode-cn.com/

值得一提的是,现在中文LeetCode【力扣】 还支持同步英文网站的账号数据,但是就个人而言,英语过得去的还是建议上英文,因为里面的功能比中文网多一点,而且最重要的是,Discuss里面的人数也会多一些,经常能看到NB的解法,还是很有帮助的。

那么为什么刷题还要写文章记录下来呢?

其实这篇文章的题目我在两年前就已经做过了,但是今天重新看,发现还是需要花很多时间去想解法,一方面当然是因为没有坚持做算法题,思维跟不上,另外一方面就是当时做完就算了,没有进一步思考,除了自己的这个解法,是否还有更好的方法。

因此我选择了把思考和改进的过程记录下来,当然大家用笔记类的工具记录,或者放到Github上都可以,目的都是为了锻炼自己的思维,提高算法水平罢了。

我当时的提交记录:

Snip20190211_2.png

我打败了58%的人,那么前面的算法是怎么样的呢?

之前使用的是Java,那么如果换成C,C++,Python等语言,结果又是怎么样呢?

除了算法之外,是不是也有一些编程语言的技巧呢?

通过进一步的思考,我们会发现越来越多可以深入学习的地方。

因此,我决定把一部分题目写成博客,初衷就是为了方便自己,如果正好也能给予他人一点帮助的话,那就更好了。

219.Contains Duplicate II

难度: Easy 分类:Array

题目

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.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

翻译:

给定一个数组和一个整数k,找出是否存在两个不同下标i和j,满足nums[i] = nums[j],并且这两个数字的绝对值不大于k。

解答

思路:

  1. 根据题目可知:我们需要一个数组和一个整形,返回值是Boolean类型的。
1
2
3
4
5
6
7
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
boolean isTrue = false;

return isTrue;
}
}
  1. 然后我们要找出是否存在满足题目条件的两个数,这里我的想法是使用一个HashMap来存储下标,然后遍历找出满足条件的数组下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
boolean isTrue = false;
// Setp 2
HashMap<Integer,Integer> hashMap = new HashMap<>();
// 通过遍历数组,把数组的值存到HashMap中,再找后面是否存在值一样,而且下标差值<=k的数,有的话返回 true
for(int i=0;i<nums.length;i++){
if(hashMap.containsKey(nums[i]) && i - hashMap.get(nums[i]) <= k){
isTrue = true;
}else {
hashMap.put(nums[i], i);
}
}
return isTrue;
}
}
  1. 考虑边界条件,虽然这样做就可以达到题目的要求了,但是提交的时候没能通过test cast,原因是没有考虑到当数组大小<=1的情况,加上这个条件,最终我的提交结果为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
boolean isTrue = false;
// Step 3
if(nums.length<=1){
return isTrue;
}
HashMap<Integer,Integer> hashMap = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(hashMap.containsKey(nums[i]) && i - hashMap.get(nums[i]) <= k){
isTrue = true;
}else {
hashMap.put(nums[i], i);
}
}
return isTrue;
}
}

这个解答的时间是:11ms,打败了58%的人,那么有没有更简单更好的解答呢?

思考

这个是LeetCode Discuss上的解答,经过我在LeetCode上Run Code,Runtime为 0 ms

1
2
3
4
5
6
7
8
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);
if(!set.add(nums[i])) return true;
}
return false;
}

思路:

同样是通过遍历数组,

  1. 如果i>k,那么说明前面的值已经不满足|i-j| <= k 的条件,可以移除 i-k-1的值
  2. 然后再判断,如果发现,咦,有一个数已经在集合里面了,我没办法加进去, set.add() 返回的是 false,那么这个数就是符合题目要求的,存在这样的数,因此我们直接 return true

我们来看看HashSet的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* this set contains no element <tt>e2</tt> such that
* <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

通过这个方法就可以判断当前元素是否已经在集合里面了。

其实这个解法的思路和我的解法是大同小异的,但是代码写得很巧妙,值得学习的地方有好几个:

  1. 通过set.add()的方法来判断,不需要 i - hashMap.get(nums[i]) <= k
  2. 通过set.remove(nums[i-k-1]) 来移除不满足条件的数字,而不是像我的方法,通过add,再一个个判断,减少了工作量

  3. 除了学习算法思路以外,也可以学习到集合的一些源码和实现,也就是数据结构的知识

C++ 解法 - Runtime: 8 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> st;
for (int i = 0; i < nums.size(); i++) {
if (i > k) {
st.erase(nums[i - k - 1]);
}
if (!st.insert(nums[i]).second) {
return true;
}
}
return false;
}
};

Python解法 - Runtime: 24 ms

1
2
3
4
5
6
7
def containsNearbyDuplicate(self, nums, k):
dic = {}
for i, v in enumerate(nums):
if v in dic and i - dic[v] <= k:
return True
dic[v] = i
return False

总结

今年立下的目标就是巩固基础,包括设计模式,算法与数据结构,学习第三方框架源码等,每天都要进步一点点,量变引起质变!与大家共勉!


本文结束啦感谢您的阅读