【leetcode每日一题】——2903. 找出满足差值条件的下标 I——python

给你一个下标从 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

方法一：

由于是简单题，并且数据量小所以直接暴力模拟就可以了：

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

 时间复杂度：最坏情况下是o（n^2),其中n是数组nums长度。

空间复杂度：由于没用到其他数组或变量，空间复杂度是o（1）的。

方法二：

有没有方法能实现一边遍历呢？是有的。

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        min1 = inf; max1 = -inf
        for j in range(indexDifference,len(nums)):
            i = j - indexDifference
            if abs(nums[j] - nums[i]) >= valueDifference:
                return [i, j]
            if min1 > nums[i]:
                min1_index = i
                min1 = nums[i]
            if max1 < nums[i]:
                max1 = nums[i]
                max1_index = i
            max1 = max(max1,nums[i])
            if abs(nums[j] - max1) >= valueDifference:
                return [max1_index,j]
            if abs(nums[j] - min1) >= valueDifference:
                return [min1_index,j]
        return [-1,-1]

 通过这段代码，不难看出一个思路，我们在遍历数组nums时，同时维护最大值和最小值，并且保证最大值和最小值的下标小于等于j 减 indexDifference，那么就能保证第一个条件，并且贪心的去求第二个条件。为什么这么做是对的呢？因为当j - i 最小是indexDifference时，比 i 还要小于等于的下标是一定满足条件的。这么一来答案就能正确。

时间复杂度：o（n），n是数组nums的长度。

空间复杂度：由于只用了一些变量，所以是o（1）的。