LeetCode 题解工作台
找出满足差值条件的下标 II
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。 你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ： abs(i - j) >= indexDifference…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
class Solution: def findIndices(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个下标从 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 <= 1050 <= nums[i] <= 1090 <= indexDifference <= 1050 <= valueDifference <= 109
解题思路
方法一
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]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n) to O(n log n) depending on whether auxiliary structures like balanced trees are used for min/max tracking. Space complexity depends on window size and tracking structures but is typically O(indexDifference) for the sliding window. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on how to maintain a candidate range efficiently as i increments.
- question_mark
Watch for missed edge cases when indexDifference is zero or large.
- question_mark
Expect discussion on early termination and value tracking optimizations.
常见陷阱
外企场景- error
Comparing all pairs blindly leads to O(n^2) time which fails large constraints.
- error
Not updating the sliding window properly can cause invalid index selections.
- error
Forgetting to handle indexDifference = 0 or valueDifference = 0 allows invalid pairs.
进阶变体
外企场景- arrow_right_alt
Find all valid pairs instead of the first pair using the same two-pointer scan.
- arrow_right_alt
Use a hash map to track previously seen values to quickly check valueDifference constraints.
- arrow_right_alt
Extend the problem to multidimensional arrays with Manhattan distance as indexDifference.