What is the time complexity of the brute-force solution for this problem?

The brute-force solution has a time complexity of O(n^2), as it involves checking all pairs of indices in the array.

How can I optimize the brute-force approach for this problem?

You can optimize the brute-force approach by using a two-pointer technique to reduce unnecessary comparisons and improve efficiency.

How does two-pointer scanning apply to this problem?

Two-pointer scanning allows you to reduce the search space by maintaining a valid range of indices that satisfy the difference conditions.

What happens if no valid indices are found in the array?

If no valid indices are found, return [-1, -1] as the output, indicating no solution exists.

What is the pattern behind this problem's solution?

This problem relies on two-pointer scanning with invariant tracking to efficiently find a pair of indices that satisfy the required differences.

#2903

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

找出满足差值条件的下标 I

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ： abs(i - j) >= indexDifference…

数组双指针

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

abs(i - j) >= indexDifference 且
abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能相等。

示例 1：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。

示例 2：

输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。 
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。 
因此，[0,0] 是一个符合题目要求的答案。 
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。

示例 3：

输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。

提示：

1 <= n == nums.length <= 100
0 <= nums[i] <= 50
0 <= indexDifference <= 100
0 <= valueDifference <= 50

lightbulb

解题思路

方法一：双指针 + 维护最大最小值

我们用两个指针 $i$ 和 $j$ 来维护一个间隔为 $indexDifference$ 的滑动窗口，其中指针 $j$ 和 $i$ 分别指向窗口的左右边界。初始时 $i$ 指向 $indexDifference$ ，而 $j$ 指向 $0$ 。

我们用 $mi$ 和 $mx$ 来维护指针 $j$ 左侧区间的最小值下标和最大值下标。

当指针 $i$ 向右移动时，我们需要更新 $mi$ 和 $mx$ 。如果 $nums[j] < nums[mi]$ ，则 $mi$ 更新为 $j$ ；如果 $nums[j] > nums[mx]$ ，则 $mx$ 更新为 $j$ 。更新完 $mi$ 和 $mx$ 后，我们就可以判断是否找到了满足条件的下标对。如果 $nums[i] - nums[mi] \geq valueDifference$ ，则找到了满足条件的下标对 $[mi, i]$ ；如果 $nums[mx] - nums[i] \geq valueDifference$ ，则找到了满足条件的下标对 $[mx, i]$ 。

如果指针 $i$ 移动到了数组的末尾，说明没有找到满足条件的下标对，返回 $[-1, -1]$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def findIndices(
        self, nums: List[int], indexDifference: int, valueDifference: int
    ) -> List[int]:
        mi = mx = 0
        for i in range(indexDifference, len(nums)):
            j = i - indexDifference
            if nums[j] < nums[mi]:
                mi = j
            if nums[j] > nums[mx]:
                mx = j
            if nums[i] - nums[mi] >= valueDifference:
                return [mi, i]
            if nums[mx] - nums[i] >= valueDifference:
                return [mx, i]
        return [-1, -1]

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates familiarity with both brute-force and optimized solutions.
question_mark
The candidate considers edge cases such as arrays with small lengths or when no solution exists.
question_mark
The candidate may discuss trade-offs between clarity and efficiency in choosing the solution.

warning

常见陷阱

外企场景

error
Relying too heavily on the brute-force approach without considering optimization strategies like two-pointer scanning.
error
Forgetting to handle edge cases like when the array is very small or when no valid pair can be found.
error
Incorrectly assuming that the two-pointer approach always works for every problem; ensuring correct invariant tracking is crucial.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there is a constraint that both indexDifference and valueDifference are always 0?
arrow_right_alt
How would the problem change if the array is sorted?
arrow_right_alt
What happens if nums contains duplicate values?

help

常见问题

外企场景

继续练习

#2905 找出满足差值条件的下标 II #2856 删除数对后的最小数组长度 #2970 统计移除递增子数组的数目 I