220.md

Contains Duplicate III

Description

link

---

Solution

假设有一个桶形式的字典，key是当前数字范围（by index），value是具体的nums（by nums），桶之间的size是t + 1，所以对于每个数字，如果存在满足条件的另外一个数字，则必然在这个桶或者相邻的桶中

最后一个i >= k判断的是将所有index不满足条件的桶中数字全部删除，保证只要存在即满足题目条件

---

Code

O(nlogn)

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if t < 0: return False
        d = {}
        for i in range(len(nums)):
            m = nums[i] // (t + 1)
            if m in d or (m - 1 in d and nums[i] - d[m - 1] <= t) or (m + 1 in d and d[m + 1] - nums[i] <= t):
                return True
            d[m] = nums[i]
            if i >= k: del d[nums[i - k] // (t + 1)]
        return False