220. Contains Duplicate III

Loading...LeetCode

Brute Force

需要验证两个bound，k和t，直接 brute force iterative 的话很简单，做个长度<=k 的窗口，在nums里滑动，窗口里每个元素都拿来跟头个元素比较一遍，时间复杂度在O(kn)，会TLE。

HashMap

这题没给具体数据规模，没法推测t/k谁更小，只能尝试下有没有O(tn)解。需要把比较的元素范围限制在 t 级别，那就不能只以 index 来设置遍历了，需要有办法按元素数值遍历，同时做到反向检索index，所以需要hashmap。

先把nums反向 hash 成一个元素数值为 key、index 为 value 的 map ，然后再对nums进行遍历，对于每个元素n，它 t bound 内的 2t 个元素与 map 的交集里是否有符合 k bound 的，有即返回True。

但事实上，提前做好整个map的话还会出错，因为可能有重复元素，导致同一数值的 index 被覆盖，这样就无法准确判断 k bound（可能存在的正确解被覆盖了）。解决方法是 hashmap 和遍历同时做，只验证已经 hash 过的元素，这样也是相当于对当前元素 n 左边的元素设置了个 [num-t, num+t] 的 filter，然后再验证 k bound。因为 n 在验证完后也还是会加入 map，所以不会漏掉。

BST

还有对数级复杂度的方法，需要 sorted nums ，

Python的确没有 TreeSet 的包，不过可以用 sortedcontainer 来实现一个 sorted list ，然后 bisect 来实现 ceiling 和 floor 操作，对于长度限制在k的BST，也都一样是 O(logk) 复杂度。然后对 nums 遍历，总共也就是 O(nlogk)，实际测试下来，对于 leetcode 的test cases，并没有 O(tn) 快。

Brute Force - TLE

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        for i in range(len(nums)):
            for j in range(max([i-k, 0]), i):
                if abs(nums[i]-nums[j]) <= t:
                    return True
        return False

Hashmap - O(tn)

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        backID = {}
        for idx, n in enumerate(nums):
            if len(backID) > 2*t:
                for m in [x for x in range(n-t, n+t+1) if x in backID]:
                    if idx-backID[m] <= k:
                        return True
            else:
                for m in backID:
                    if abs(n-m) <= t and idx-backID[m] <= k:
                        return True
            backID[n] = idx
        return False

Binary Search

import sortedcontainers
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        
        def floor(n, bst):
            le = bst.bisect_right(n) - 1
            return bst[le] if le >= 0 else None
        
        def ceiling(n, bst):
            ge = bst.bisect_right(n)
            return bst[ge] if ge < len(bst) else None
        
        bst = sortedcontainers.SortedList()
        for i, n in enumerate(nums):
            le = floor(n, bst)
            if le and n <= le + t: return True
            ge = ceiling(n, bst)
            if ge and ge <= n + t: return True
            bst.add(n)
            if len(bst) > k: bst.remove(nums[i-k])
        return False