LeetCode讲解篇之220. 存在重复元素 III

题目描述

题解思路

我们可以考虑存储数组中连续indexDiff个数字，这样我们只需要在这连续的indexDiff个数字中查找相差小于等于valueDiff的两个数字的问题
对于该查找问题，我们可以考虑使用以valueDiff大小为一个桶，如果我们当前加入桶的数字已经存在或者相邻桶的数字的差值是否小于等于valueDiff，则说明存在满足条件的下标对
如果数组遍历完毕后，未找到满足条件的下标对，则没有满足条件的下标对

题解代码

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        n = len(nums)
        m = dict()
        for i in range(n):
            # 计算当前数字放入哪个桶中
            id = nums[i] // (valueDiff + 1)

            if id in m: 
                # 存在和当前数在一个桶内的数字，表明找到满足条件的下标对
                return True
            if (id - 1) in m and abs(m[id - 1] - nums[i]) <= valueDiff:
                # 当前数字的前一个桶中的数字和当前数字的差值绝对值小于等于valueDiff，表明找到满足条件的下标对
                return True
            if (id + 1) in m and abs(m[id + 1] - nums[i]) <= valueDiff:
                # 当前数字的后一个桶中的数字和当前数字的差值绝对值小于等于valueDiff，表明找到满足条件的下标对
                return True
            
            # 当前数字放入桶中
            m[id] = nums[i]

            # 淘汰前indexDiff个数字所在的桶
            if i >= indexDiff:
                m.pop(nums[i - indexDiff] // (valueDiff + 1))

        return False

原文地址：https://blog.csdn.net/qq_67733273/article/details/142405287

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！