找出满足差值条件的下标 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

/*
 * 思路：
 * 使用流式API，通过两个流生成所有的下标对(i, j)
 * 过滤出满足条件的下标对
 * 使用findFirst获取第一个满足条件的下标对，或者返回[-1, -1]
 */
import java.util.stream.IntStream;

public class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        return IntStream.range(0, nums.length)
                .boxed()
                .flatMap(i -> IntStream.range(0, nums.length).mapToObj(j -> new int[]{i, j}))
                .filter(pair -> Math.abs(pair[0] - pair[1]) >= indexDifference && Math.abs(nums[pair[0]] - nums[pair[1]]) >= valueDifference)
                .findFirst()
                .orElse(new int[]{-1, -1});
    }
}

此题解采用了暴力方法来寻找符合条件的下标对。它通过两层循环遍历数组 nums 中的所有可能的下标对 (i, j)，检查每对下标是否满足条件 abs(i - j) >= indexDifference 和 abs(nums[i] - nums[j]) >= valueDifference。如果找到符合条件的下标对，就立即返回这一对下标；如果遍历结束后没有找到符合条件的下标对，则返回 [-1, -1]。

O(n^2)

O(1)