What is the sliding window technique in Contains Duplicate III?

The sliding window technique helps to efficiently track elements within a range of indices. It limits the number of elements checked at once, which is critical for optimizing performance in problems like Contains Duplicate III.

How do I handle edge cases in Contains Duplicate III?

Edge cases include arrays of small length or situations where no valid pair satisfies the constraints. Properly managing the window size and handling these cases is essential to solving the problem correctly.

What is the time complexity of the sliding window approach for Contains Duplicate III?

Using a sliding window with an efficient data structure results in a time complexity of O(n log k), where n is the length of the array and k is the window size.

How do ordered sets help in solving Contains Duplicate III?

Ordered sets allow for fast lookups and updates, ensuring that we can efficiently check if the current window meets the valueDiff condition. They help maintain an optimized solution for larger arrays.

What are the potential pitfalls when solving Contains Duplicate III?

Common pitfalls include failing to use the correct data structure to manage the sliding window, neglecting edge cases, and not optimizing for large input sizes, leading to suboptimal performance.

#220

Hard

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

存在重复元素 III

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。找出满足下述条件的下标对 (i, j) ： i != j , abs(i - j) abs(nums[i] - nums[j]) 如果存在，返回 true ；否则，返回 false 。示例 1：输入： nu…

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

题目描述

给你一个整数数组 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⁹

lightbulb

解题思路

方法一：滑动窗口 + 有序集合

我们维护一个大小为 $k$ 的滑动窗口，窗口中的元素保持有序。

遍历数组 nums，对于每个元素 $nums[i]$ ，我们在有序集合中查找第一个大于等于 $nums[i] - t$ 的元素，如果元素存在，并且该元素小于等于 $nums[i] + t$ ，说明找到了一对符合条件的元素，返回 true。否则，我们将 $nums[i]$ 插入到有序集合中，并且如果有序集合的大小超过了 $k$ ，我们需要将最早加入有序集合的元素删除。

时间复杂度 $O(n \times \log k)$ ，其中 $n$ 是数组 nums 的长度。对于每个元素，我们需要 $O(\log k)$ 的时间来查找有序集合中的元素，一共有 $n$ 个元素，因此总时间复杂度是 $O(n \times \log k)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def containsNearbyAlmostDuplicate(
        self, nums: List[int], indexDiff: int, valueDiff: int
    ) -> bool:
        s = SortedSet()
        for i, v in enumerate(nums):
            j = s.bisect_left(v - valueDiff)
            if j < len(s) and s[j] <= v + valueDiff:
                return True
            s.add(v)
            if i >= indexDiff:
                s.remove(nums[i - indexDiff])
        return False

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of sliding window techniques combined with efficient state management.
question_mark
Assess the candidate's ability to handle edge cases where no valid pair exists.
question_mark
Evaluate the candidate's knowledge of data structures like ordered sets or bucket sorts for optimization.

warning

常见陷阱

外企场景

error
Overlooking the need for an efficient data structure to track the sliding window.
error
Failing to properly manage the constraints, especially when dealing with large inputs.
error
Incorrectly handling edge cases, such as when the valueDiff is zero or when no valid pair exists.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow a larger range for indexDiff and valueDiff, making the sliding window approach more complex.
arrow_right_alt
Limit the array length, requiring optimization of both space and time complexity.
arrow_right_alt
Implement the solution without relying on specific data structures like ordered sets, which may require a brute-force approach.

help

常见问题

外企场景

继续练习

#347 前 K 个高频元素 #594 最长和谐子序列 #632 最小区间