Easy

题目描述

给你一个长度为 n 的 0 索引 整数数组 nums、一个整数 indexDifference 和一个整数 valueDifference。

你的任务是找到两个索引 i 和 j，两者都在范围 [0, n - 1] 内，并且满足下述条件：

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

返回整数数组 answer，其中 answer = [i, j] 是满足上述条件的两个索引。如果不存在满足条件的两个索引，则返回 [-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]
解释：在这个例子中，可以证明不可能找到满足两个条件的两个索引。
因此，返回 [-1,-1]。

约束条件：

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

解题思路

解题思路

这是一道简单的数组遍历题目，由于数据规模很小（n ≤ 100），我们可以直接使用暴力解法。

方法一：暴力枚举（推荐）

  1. 使用双重循环遍历所有可能的索引对 (i, j)
  2. 对于每个索引对，检查是否同时满足两个条件：
    • 索引差值条件：abs(i - j) >= indexDifference
    • 数值差值条件：abs(nums[i] - nums[j]) >= valueDifference
  3. 一旦找到满足条件的索引对，立即返回
  4. 如果遍历完所有可能的索引对都没找到，返回 [-1, -1]

方法二：优化暴力枚举 由于索引差值条件的存在，对于固定的索引 i，我们只需要检查与 i 距离至少为 indexDifference 的索引 j。这样可以减少一些不必要的比较，但时间复杂度仍然是 O(n²)。

由于题目数据范围很小且要求返回任意一个满足条件的解，暴力枚举是最直接有效的方法。

代码实现

class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (abs(i - j) >= indexDifference && abs(nums[i] - nums[j]) >= valueDifference) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }
};

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

public class Solution {
    public int[] FindIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.Length;
        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) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {-1, -1};
    }
}

var findIndices = function(nums, indexDifference, valueDifference) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {
                return [i, j];
            }
        }
    }
    return [-1, -1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值说明
时间复杂度O(n²)双重循环遍历所有索引对
空间复杂度O(1)只使用常数额外空间

相关题目