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

总结

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

本文结束啦感谢您的阅读