本文共 2531 字，大约阅读时间需要 8 分钟。
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.
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
------------------------------------------------------------------------------
This is a good question!!! A sliding window with length t will results in TLE. Therefore, techniques for improvents are expected. Bucket partition is a good choice here. Cut nums into ... [0, t] [t+1,2t+1] ..., nums in the same bucket are obviously true. For every num, it's impossible to put 2 nums in the same adjacent bucket. So it has at most 1 num standing for the adjacent bucket. That's enough for this problem.
class Solution: def containsNearbyAlmostDuplicate(self, nums, k, t): d = {} w = t+1 for i in range(len(nums)): bid = nums[i] // w if (bid in d): return True elif (bid-1 in d and abs(d[bid-1]-nums[i]) <= t): return True elif (bid+1 in d and abs(d[bid+1]-nums[i]) <= t): return True d[bid] = nums[i] #bug3: 忘了 if (i>=k): #bug1: 这次有效，下次就无效的桶 d.pop(nums[i-k] // w) #bug2: i-k，瞎啊 return Falses = Solution()print(s.containsNearbyAlmostDuplicate([1,2,3,1],3,0))print(s.containsNearbyAlmostDuplicate([1,0,1,1],1,2))print(s.containsNearbyAlmostDuplicate([1,5,9,1,5,9], 2, 3)) Another solution is maintaining the sliding window as BST. BST requires 4 operations: getCeiling, getFloor, insert, remove(k). In c++, set (insert, erase, upper_bound, lower_bound) could be used. In java, TreeSet could be used. In Python, no corresponding object for the time being.
Copy from discussion:
bool containsNearbyAlmostDuplicate(vector & nums, int k, int t) { set window; // set is ordered automatically for (int i = 0; i < nums.size(); i++) { if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k // |x - nums[i]| <= t ==> -t <= x - nums[i] <= t; auto pos = window.lower_bound(nums[i] - t); // x-nums[i] >= -t ==> x >= nums[i]-t // x - nums[i] <= t ==> |x - nums[i]| <= t if (pos != window.end() && *pos - nums[i] <= t) return true; window.insert(nums[i]); } return false;}
转载地址：http://ftfoi.baihongyu.com/