存在重复元素 III（LeetCode）

本文主要是介绍存在重复元素 III（LeetCode），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

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

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

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

解题

"""
该算法的时间复杂度为 O(n log min(n, indexDiff))，其中 n 是数组的长度。
SortedList 的插入和删除操作均为 O(log k)，k 为当前滑动窗口的大小
"""
from sortedcontainers import SortedListdef containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff):# 有序列表，用于维护滑动窗口内的元素sorted_list = SortedList()for i, num in enumerate(nums):# 如果有滑动窗口大小限制，移除不在窗口内的元素if i > indexDiff:sorted_list.remove(nums[i - indexDiff - 1])# 查找范围内是否存在符合条件的元素pos1 = sorted_list.bisect_left(num - valueDiff)if pos1 < len(sorted_list) and sorted_list[pos1] <= num + valueDiff:return True# 将当前元素加入有序列表中sorted_list.add(num)return Falsenums = [1, 2, 3, 1]
indexDiff = 3
valueDiff = 0
print(containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff))  # 输出: True

这篇关于存在重复元素 III（LeetCode）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---