[LeetCode] 220. Contains Duplicate III

轉自LeetCode

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.

<Solution>
Contains Duplicate II 的再度衍生

這次要找的不是數值相同而已，而是絕對數值差在 t 以內都可以

思考方向

• 運用 bucket 的概念來檢查是否差值在 t 以內。例如 bucket 的大小為 3，則 [0,3] 這個 bucket 可以包涵 0,1,2，差值都是在 3 以內

• 在檢查的時候，也要檢查前後的 bucket。例如 2 和 4 分別在 [0,3] 和 [3,6] 這兩個不同 bucket，可是他們差值依然小於 3

• 因為落在哪個 bucket 會使用除法，如果分子為負數的話，則全部都會落在第一個 bucket，所以先將每個數減掉 int 的最小值，來都變成正數

code 如下

C++
Java
kotlin