0219.Contains_Duplicate_II.py

"""
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

 

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false
 

Constraints:

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105
"""

#hash 

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        posDict = collections.defaultdict(int)
        for i, num in enumerate(nums):
            if num in posDict:
                if i - posDict[num] <= k:
                    return True
            posDict[num] = i
        return False
            
#sliding window

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        numSet = set()
        j = 0
        for i in range(len(nums)):
            while j < len(nums) and j - i <= k:
                if nums[j] in numSet:
                    return True
                numSet.add(nums[j])
                j += 1
            numSet.remove(nums[i])
        return False