[LeetCode] 2903. Find Indices With Index and Value Difference I

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;
    }
}