動機

很喜歡的一題，看到怎麼處理abs

Problem

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

 

Example 1:

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

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2Output: true

Example 3:

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

 

Constraints:

  • 0 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 104
  • 0 <= t <= 231 - 1

Sol

index的abs用windows len去限制

資料的abs要推

abs(nums[i] - nums[j]) <= t
-t <= nums[i] - nums[j] <= t
-t-nums[i] <= - nums[j] <= t-nums[i]
t+nums[i] >= nums[j] >= nums[i]-t
nums[j] >= nums[i]-t 第一個大於等於，lower bound

剩下就是另外檢查

from sortedcontainers import SortedList
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        win = SortedList()
        
        j=0
        for i in range(len(nums)):
            x = bisect_left(win,nums[i]-t)
            if x < len(win) and abs(nums[i]-win[x]) <= t:
                return True

            # update window
            win.add(nums[i])
            if len(win) > k:
                win.remove(nums[j])
                j += 1
        return False