<jupyter_start><jupyter_text>![image.png](attachment:image.png)http://bookshadow.com/weblog/2015/06/03/leetcode-contains-duplicate-iii/https://leetcode.com/problems/contains-duplicate-iii/discuss/118278/python-O(n)-solution-using-buckets-pigeon-hole-principleGiven an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.Example 1:Input: nums = [1,2,3,1], k = 3, t = 0Output: trueExample 2:Input: nums = [1,0,1,1], k = 1, t = 2Output: trueExample 3:Input: nums = [1,5,9,1,5,9], k = 2, t = 3Output: false<jupyter_code>import collections

def containsNearbyAlmostDuplicate(nums, k, t):
    if k < 1 or t < 0:
        return False
    window = collections.OrderedDict()
    for x in range(len(nums)):
        key = nums[x] // max(1, t)
        for m in (key, key - 1, key + 1):
            if m in window and abs(nums[x] - window[m]) <= t:
                return True
        window[key] = nums[x]
        if x >=  k:   #因為numDict是個window,所以當他大於k,也就是window的大小時，必須把前面的pop掉,而popitem(last=False)就是指
                      #把第一個數字pop掉，在此也說明為什麼要用Ordered Dictionary，因為要儲存數列順序。
            window.popitem(last=False)
    return False

nums = [7,1,3]
k = 2
t = 3
containsNearbyAlmostDuplicate(nums,k,t)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12617159336697908, 'fraction_numerical': 0.033886085075702954, 'mean_word_length': 3.463022508038585, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 6, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '148411', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 565, 'n_tokens_neox': 540, 'n_words': 127, 'path': '220. Contains Duplicate III.ipynb', 'repo_name': 'kkoo1122/Leetcode_Practice', 'size': '1387'}