Contain Duplicate

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.

思想：使用哈希表存储最近出现的k个元素，对于每个元素检查其是否在哈希表中即可。
做法步骤：

1. 初始时哈希表为空
2. 对于每一个元素i，检查其是否在哈希表中，如果是则返回。
3. 如果不是，则将其插入到哈希表中
4. 当哈希表元素超过k个时，删除第i-k个元素

def containsNearbyDuplicate(nums, k):
    if k == 0:
        return False
    dic = {}
    for i, num in enumerate(nums):
        if num in dic:
            return True
        dic[num] = i
        if i >= k:
            del dic[nums[i-k]]
    return False

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

这一题是对上一题的扩展，允许元素的差值最大为k。
思想：每个元素除以t后得到v，仅需检查[v/t-1, v/t, v/t+1]这三个值是否在哈希表中即可判断是否存在差值小于k的元素

做法步骤：将每个元素值num除以t存入哈希表中。哈希表存储最近k个元素。

1. 初始时哈希表为空
2. 对于每一个元素i，将其除以t，得到key。
3. 检查[key-1, key, key+1]是否在哈希表中存在。如果存在，检查其实际值的差是否小于t
4. 如果不存在，将val存入哈希表中，并记录其实际值: dict[num[i]/t] = num[i]
5. 当哈希表元素超过k个时，删除第i-k个元素

当t等于0时，需要进行特殊处理。此时key=num

def containsNearbyAlmostDuplicate(self, nums, k, t):
    if k < 1 or t < 0:
        return False
    dic = {}
    for i, num in enumerate(nums):
        key = num / t if t else num
        for v in [key-1, key, key+1]:
            if v in dic and abs(dic[v] - num) <= t:
                return True
        if len(dic) == k:
            prevKey = nums[i-k] / t if t else nums[i-k]
            del dic[prevKey]
        dic[key] = num
    return False