存在重复元素 III

标签: 数组 桶排序 有序集合 排序 滑动窗口

难度: Medium

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

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

注意：本题与主站 220 题相同： https://leetcode-cn.com/problems/contains-duplicate-iii/

Submission

运行时间: 29 ms

内存: 18.4 MB

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        def getId(x, w):
            return x//w if x >= 0 else x//w-1

        dic = {}
        for i, n in enumerate(nums):
            if i > k:
                del dic[getId(nums[i-k-1], t+1)]
            aid = getId(n, t+1)
            if aid in dic:
                return True
            if aid+1 in dic and abs(n - dic[aid+1]) <= t:
                return True
            if aid-1 in dic and abs(n- dic[aid-1]) <= t:
                return True
            dic[aid] = n
        return False

Explain

此题解采用了桶排序思想和滑动窗口的结合来解决问题。首先，定义一个桶的映射方法getId，该方法将每个数字映射到一个桶ID，其中每个桶的范围是大小为t+1的区间。然后，遍历数组，对于每个元素，检查其所在的桶及相邻桶是否存在满足条件的元素。如果数组索引i大于k，为了维护大小为k的窗口，将窗口外的元素从字典中移除（即删除过期的桶）。通过这种方式，我们保证了检查的元素总是在k距离内的元素，并通过桶的映射减少了比较的次数，从而提高了效率。

时间复杂度: O(n)

空间复杂度: O(k)

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        def getId(x, w):
            # 计算桶ID，对于负数需要额外处理以保证正确映射
            return x//w if x >= 0 else x//w-1

        dic = {} # 存储(桶ID: 元素值)的映射
        for i, n in enumerate(nums):
            if i > k: # 维护大小为k的滑动窗口，删除窗口前元素对应的桶
                del dic[getId(nums[i-k-1], t+1)]
            aid = getId(n, t+1) # 计算当前元素的桶ID
            if aid in dic: # 检查同一个桶内是否已经有元素
                return True
            if aid+1 in dic and abs(n - dic[aid+1]) <= t: # 检查右邻桶
                return True
            if aid-1 in dic and abs(n - dic[aid-1]) <= t: # 检查左邻桶
                return True
            dic[aid] = n # 更新当前桶ID的值
        return False

Explore

桶排序的思路被用于此算法中是为了高效地处理和维护元素与其索引之间的关系，同时确保可以快速比较元素差的大小是否满足条件。结合滑动窗口的方法，可以保证我们只在一个固定大小为k的窗口内进行比较，从而满足条件`abs(i - j) <= k`。这种结合使用减少了不必要的比较，提高了算法的效率，并且便于处理和更新元素。将元素分配到桶中，使得每个桶内的元素值之间的差异很小（不超过t），这样可以快速定位并判断是否有符合条件的元素对。

桶的大小设置为`t + 1`是为了确保桶内的任何两个元素的差值绝对不会大于`t`。这样的设置可以保证如果两个元素在同一个桶内，它们的差值必然满足`abs(nums[i] - nums[j]) <= t`。此外，这种设置也便于处理元素可能跨桶比较的情况，只需要检查相邻的桶即可（当前桶及左右各一个桶），这样可以保证覆盖所有可能的满足条件的元素对，因为即使两个元素处在不同桶，只要它们的差值小于等于t，它们也会被检查到。

检查`i > k`而不是`i >= k`是为了确保在删除桶之前，窗口内始终保持最多k个元素。当`i = k`时，元素从0到k（共k+1个元素）都在窗口内，删除第0个元素是在处理第k+1个元素时进行的，即`i = k+1`时，保证窗口内只有k个元素。这种处理方式是为了维护正确的窗口大小和确保不会过早地删除元素，确保所有在窗口大小k范围内的元素都被比较，保持算法的正确性。