You are given a 0-indexed integer array nums having length n, an integer indexDifference, and an integer valueDifference.
Your task is to find two indices i and j, both in the range [0, n - 1], that satisfy the following conditions:
abs(i - j) >= indexDifference, and
abs(nums[i] - nums[j]) >= valueDifference
Return an integer array answer, where answer = [i, j] if there are two such indices, and answer = [-1, -1] otherwise. If there are multiple choices for the two indices, return any of them.
Note: i and j may be equal.
Example 1:
Input: nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
Output: [0,3]
Explanation: In this example, i = 0 and j = 3 can be selected.
abs(0 - 3) >= 2 and abs(nums[0] - nums[3]) >= 4.
Hence, a valid answer is [0,3].
[3,0] is also a valid answer.
Example 2:
Input: nums = [2,1], indexDifference = 0, valueDifference = 0
Output: [0,0]
Explanation: In this example, i = 0 and j = 0 can be selected.
abs(0 - 0) >= 0 and abs(nums[0] - nums[0]) >= 0.
Hence, a valid answer is [0,0].
Other valid answers are [0,1], [1,0], and [1,1].
Example 3:
Input: nums = [1,2,3], indexDifference = 2, valueDifference = 4
Output: [-1,-1]
Explanation: In this example, it can be shown that it is impossible to find two indices that satisfy both conditions.
Hence, [-1,-1] is returned.
Constraints:
1 <= n == nums.length <= 100
0 <= nums[i] <= 50
0 <= indexDifference <= 100
0 <= valueDifference <= 50
找出满足差值条件的下标 I。
给你一个下标从 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 可能 相等 。
思路一 - 暴力解
两层 for 循环，遍历所有可能的 i 和 j，判断是否满足条件。
复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)
代码
Java实现
class Solution {
public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
int n = nums.length;
int[] res = new int[] { -1, -1 };
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {
res[0] = i;
res[1] = j;
}
}
}
return res;
}
}
思路二 - 滑动窗口
一个更好的思路是使用滑动窗口。这里我们滑动窗口的尺寸是固定的，为 indexDifference。我们用一个 for 循环，遍历所有可能的 i，然后创建另一个变量 j，使得 j 和 i 的距离一直保持为 indexDifference。在遍历的过程中，因为 i 和 j 的距离满足题目的要求了，所以我们可以在遍历的过程中记录 j 遇到的最大值和最小值，当走到某个 i 位置的时候，如果发现 nums[i] - min >= valueDifference 或者 max - nums[i] >= valueDifference，我们就可以返回 [minIndex, i] 或者 [maxIndex, i]，就说明找到一个可行解了。
复杂度
时间复杂度：O(n)
空间复杂度：O(1)
代码
Java实现
class Solution {
public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
int[] res = new int[] { -1, -1 };
int j;
int max = nums[0];
int min = nums[0];
int maxIndex = 0;
int minIndex = 0;
for (int i = indexDifference; i < nums.length; i++) {
j = i - indexDifference;
if (nums[j] > max) {
max = nums[j];
maxIndex = j;
}
if (nums[j] < min) {
min = nums[j];
minIndex = j;
}
if (nums[i] - min >= valueDifference) {
return new int[] { minIndex, i };
}
if (max - nums[i] >= valueDifference) {
return new int[] { maxIndex, i };
}
}
return res;
}
}