Problem Definition:
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.
Solution 1: O(n^2) (报超时)
1 def containsNearbyDuplicate(nums, k): 2 n=len(nums) 3 if n*k==0: 4 return False 5 i=0 6 while i<n-1: 7 j=1 8 while j<=k: 9 if (i+j)>(n-1): 10 break 11 if nums[i]==nums[i+j]: 12 return True 13 else: 14 j+=1 15 i+=1 16 return False
Solution 2: 以空间换时间，遍历过程中把数组内的值和值的下标以键值对的形成保存在字典中( dict )，字典查询的时间复杂度是O(1)。
1 def containsNearbyDuplicate(self, nums, k):
2 n = len(nums)
3 if n*k==0:
4 return False
5 d = {}
6 for i in range(n):
7 if nums[i] not in d:
8 d[nums[i]] = i
9 else:
10 diff = abs(d[nums[i]]-i)
11 if diff <= k:
12 return True
13 else:
14 d[nums[i]] = i
15 return False
LeetCode#219 Contains Duplicate II
原文：http://www.cnblogs.com/acetseng/p/4652435.html