找出满足差值条件的下标 I

难度: Easy

给你一个下标从 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 <= 100
0 <= nums[i] <= 50
0 <= indexDifference <= 100
0 <= valueDifference <= 50

Submission

运行时间: 27 ms

内存: 15.9 MB

import math
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 math.fabs(i-j)>=indexDifference and math.fabs(nums[i]-nums[j])>=valueDifference:
                    return [i,j]

        return [-1,-1]

Explain

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

时间复杂度: O(n^2)

空间复杂度: O(1)

import math

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        n = len(nums)  # 获取数组长度
        # 遍历所有可能的下标对 (i, j)
        for i in range(n):
            for j in range(n):
                # 检查下标对 (i, j) 是否满足题目条件
                if math.fabs(i - j) >= indexDifference and math.fabs(nums[i] - nums[j]) >= valueDifference:
                    return [i, j]  # 如果满足条件，立即返回结果

        return [-1, -1]  # 如果没有符合条件的下标对，返回 [-1, -1]

Explore

暴力方法通常是解决算法问题的最直接和最简单的方法，尤其是在问题的规模较小或者问题的约束条件比较复杂时。在本题中，由于需要同时考虑索引差和值差的条件，可能会使得使用哈希表或排序方法的实现相对复杂，需要特殊的数据结构或额外的逻辑来同时满足两个条件。暴力方法虽然时间复杂度较高，但易于实现和理解。此外，暴力解法也可以作为其他方法的验证基准，确保更复杂的方法在设计时没有遗漏特殊情况。

在这种暴力解法中，的确存在因两层循环而导致的性能问题，尤其是当数组长度非常大时，时间复杂度会达到O(n^2)，这对于大数据量的情况是不切实际的。这种方法在小规模数据的情况下是可行的，但在实际应用中，特别是处理大数据时，应该考虑更高效的算法或数据结构以优化性能。

在Python中，`abs()`函数确实可以直接用于整数和浮点数，并且能够返回其绝对值。因此，在这种情况下使用`math.fabs`不是必要的，直接使用内建的`abs()`函数更为简洁和高效。通常`math.fabs()`用于确保操作的数值类型为浮点数，但在处理整数差值时，`abs()`完全足够。

题目和代码中未对`indexDifference`或`valueDifference`为负的情况进行特别处理或说明，可能是基于假设这两个参数总是非负整数。在实际应用中，这种假设应明确指出，或者代码应该添加处理或检查这些参数的逻辑，以防止错误的输入导致程序异常。正确的做法应该是在函数开始处检查这些参数的有效性，确保它们符合预期的范围和类型。