卖萌的弱渣

I am stupid, I am hungry.

Comtains Duplicate III

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.

Solution

思路

(Contains-Duplicate3.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """

        if k < 1 or t < 0:
            return False
        Dict = collections.OrderedDict()
        for x in range(len(nums)):
            key = nums[x]/max(1,t)
            # only check three options
            for m in (key-1,key,key+1):
                if m in Dict and abs(Dict[m]-nums[x])<=t:
                    return True
            Dict[m] = nums[x]
            if x >= k:
                Dict.popitem(last=False)
        return False