0220：存在重复元素 III（★★）

Ian

2015-08-08 约 513 字预计阅读 2 分钟次阅读

力扣第 220 题

题目

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。

找出满足下述条件的下标对 (i, j)：

i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff

如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出：true
解释：可以找出 (i, j) = (0, 3) 。
满足下述 3 个条件：
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

示例 2：

输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出：false
解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。

提示：

2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10⁹

分析

#1

0219 升级版，要找的不是相同数而是一个范围内的数了

考虑维护窗口 [j-k, j-1] 有序，即可二分查找离 nums[j] 最近的数
有序窗口要进行插入、删除、查找操作，考虑用有序集合 SortedList 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        from sortedcontainers import SortedList
        sl = SortedList()
        for j,x in enumerate(nums):
            if j>indexDiff:
                sl.remove(nums[j-indexDiff-1])
            pos = sl.bisect_left(x)
            for y in sl[max(0,pos-1):pos+1]:
                if abs(x-y)<=valueDiff:
                    return True
            sl.add(x)
        return False

909 ms

#2

还有个巧妙的桶排序方法。

桶的 size 设为 t+1，维护窗口 [j-k, j-1] 的桶状态。
符合条件的数和 nums[j] 要么在一个桶，要么在相邻桶
如果某个桶有两个元素，显然已经符合了
因此每轮最多与三个桶中的唯一元素比较，时间复杂度 O(N)

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        B,w = {}, valueDiff+1
        for j,x in enumerate(nums):
            if j>indexDiff:
                B.pop(nums[j-indexDiff-1]//w)
            key = x//w
            if any(abs(B.get(k,inf)-x)<=valueDiff for k in [key,key-1,key+1]):
                return True
            B[key] = x
        return False

363 ms

目录

0220：存在重复元素 III（★★）

题目

分析

#1

#2

解答