Leetcode: Contains Duplicate III

Contains Duplicate III

Similar Problems:

Given 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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/contains-duplicate-iii
## Basic Ideas: sliding window
##              Maintain a window with k+1 elements. A set for unsorted unique collection
## Complexity: Time O(n), Space O(k)
class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        length = len(nums)
        if length <= 0: return False
        if k == 0: return False
        s = set([])
        for i in xrange(length):
            if i > k:
            for v in s:
                if abs(nums[i]-v) <= t:
                    return True
        return False

# s = Solution()
# print s.containsNearbyAlmostDuplicate([-1, -1], 1, 0) # True
# print s.containsNearbyAlmostDuplicate([-1, -1], 1, 1) # True
# print s.containsNearbyAlmostDuplicate([99, 99], 1, 1) # True
# print s.containsNearbyAlmostDuplicate([1, 2, 1], 0, 1) # False
# print s.containsNearbyAlmostDuplicate([0, 2147483647], 1, 2147483647) # True

Share It, If You Like It.

Leave a Reply

Your email address will not be published.