Python学习之妙用字典类型

从一道leetcode题目说起，题目链接：

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

  

题目描述如图：

题目很简单，理解起来也很容易，给定一个数据nums，判断是否存在这样的k索引i和j，使得nums[i] == nums[j] 且 j - i >= k，nums，k为给定的值，0<=i<=j < length，理解意思之后很容易就写出这样的代码：

   

    

     

      

     
     

      

       class Solution:
      
     
    

     

      

     
     

      
 def containsNearbyDuplicate(self, nums, k):
      
     
    

     

      

     
     

      
 """
      
     
    

     

      

     
     

      

        :type nums: List[int]
      
     
    

     

      

     
     

      

        :type k: int
      
     
    

     

      

     
     

      

        :rtype: bool
      
     
    

     

      

     
     

      

        """
      
     
    

     

      

     
     

      
 for i in range(len(nums)):
      
     
    

     

      

     
     

      
 if nums[i] in nums[i+1:i+k+1]:
      
     
    

     

      

     
     

      
 return True
      
     
    

     

      

     
     

      
 return False
      
     
   
  

我这里的思路就是直接判断 nums[i] 这个值是否在 切片数组nums[i+1:i+k+1]里面，存在则返回True，不存在则返回False，因为Python列表切片不涉及到越界的问题，所以不用去判断数组(列表)长度。

也许你会想，这也太简单了，满怀欣喜的提交，却发现 超时了。

啊。。。。。。。。。这样的是不行的，无法通过测试，那只能换一种思路了。

我们知道，Python中list对象的存储结构采用的是线性表，采用 in 这样的方式查询元素的时间复杂度是 O(n),上面的程序总的时间复杂度是O(n*k)(n表示数组长度),因此在给定的数组比较大时，会导致超时，其消耗的时间也就在于查询元素。

那有没有更快的方式的呢？有的，我们可以使用 字典类型，它查询元素的时间在最优的情况下可以达到O(1)，也就是基本不用花什么时间就能取得元素。那这样整体换算下来，程序的时间就只有O(n)

思路：新建一个字典类型，用key来保存 数组元素值，用value来保存索引值，类似哨兵的效果，即查询到元素在字典中存在时，这时新的索引减去旧的索引，如果小于给定的K值，则返回True，否则更新元素的索引值，直到访问完所有元素，代码如下：

   

    

     

      

     
     

      

       class Solution(object):
      
     
    

     

      

     
     

      
 def containsNearbyDuplicate(self, nums, k):
      
     
    

     

      

     
     

      
 """
      
     
    

     

      

     
     

      

        :type nums: List[int]
      
     
    

     

      

     
     

      

        :type k: int
      
     
    

     

      

     
     

      

        :rtype: bool
      
     
    

     

      

     
     

      

        """
      
     
    

     

      

     
     

      

        d = {}
      
     
    

     

      

     
     

      
 for i,num in enumerate(nums):
      
     
    

     

      

     
     

      
 if num in d:
      
     
    

     

      

     
     

      
 if i - d[num] <= k:
      
     
    

     

      

     
     

      
 return True
      
     
    

     

      

     
     

      

        d[num] = i
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 return False
      
     
    

     

      

     
     

      
 
      
     
   
  

再次提交，Accepted了，再也不会超时了，而且还发现这种方法居然打败了99.95%的用户。赞！

Python真是一门不掉头发的语言啊！