🔗 🟢 2903. Find Indices With Index and Value Difference I 1158

tags: `Weekly Contest 367` `暴力(Brute Force)` `雙指標(Two Pointers)`

題意

給定一個長度為 $n$ 的整數陣列 $nums$ ，以及兩個非負整數 $indexDifference$ 和 $valueDifference$ 。

找出兩個下標 $i$ 和 $j$ ，滿足以下條件：

$abs(i - j) \geq indexDifference$
$abs(nums[i] - nums[j]) \geq valueDifference$

如果存在這樣的下標，則返回 $[i, j]$ ；否則返回 $[-1, -1]$ 。

注意： $i$ 和 $j$ 可以相等。

限制

$1 \leq n == nums.length \leq 100$
$0 \leq nums[i] \leq 50$
$0 \leq indexDifference \leq 100$
$0 \leq valueDifference \leq 50$

思路

解法一：暴力法(Brute Force)

由限制可以看出數據範圍不大，因此可以直接暴力枚舉所有可能的下標對 $(i, j)$ ，檢查是否滿足條件。

此外，在枚舉 $j$ 時，可以從 $i + indexDifference$ 開始遞減，這樣可以保證 $j - i \geq indexDifference$ ，因此可以減少一些不必要的枚舉，且檢查是否滿足條件時，只需檢查 $abs(nums[i] - nums[j]) \geq valueDifference$ 即可。

複雜度分析

時間複雜度： $O(n^2)$ ，其中 $n$ 為陣列 $nums$ 的長度。
空間複雜度： $O(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(i + indexDifference, n): # j - i >= indexDifference
                if abs(nums[i]-nums[j]) >= valueDifference:
                    return [i,j]
        return [-1,-1]

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 = i + indexDifference; j < n; j++) // j - i >= indexDifference
                if (abs(nums[j] - nums[i]) >= valueDifference) 
                    return {i, j};
        return {-1, -1};
    }
};

解法二：雙指標(Two Pointers)

類似於解法一中的優化，在枚舉右指針 $j$ 時，只檢查一個左指針 $i = j - indexDifference$ ，這樣可以保證 $j - i = indexDifference$ ，且對於之前檢查過的 $i_{pre}$ ，也能夠滿足此條件。故我們必須在枚舉 $j$ 時，利用與其對應的 $i$ ，來檢查 $nums[:i+1]$ 中是否存在某個數字能夠與 $j$ 構成答案，為此我們需要維護 $nums[:i+1]$ 中的某些性質。

而若當前枚舉的 $j$ 存在答案，則根據限制條件，答案在 $nums[:i+1]$ 中，且其中的最大值或最小值必定也能成為答案，證明如下：

若存在下標 $k$ ，其中 $0 \leq k \leq i$ 使得 $[k, j]$ 滿足 $nums[k] - nums[j] \geq valueDifference$ ，則因為 $nums[idx_{max}] \geq nums[k]$ ，故 $[idx_{max}, j]$ 也滿足條件。
若存在下標 $k$ ，其中 $0 \leq k \leq i$ 使得 $[k, j]$ 滿足 $nums[j] - nums[k] \geq valueDifference$ ，則因為 $nums[idx_{min}] \leq nums[k]$ ，故 $[idx_{min}, j]$ 也滿足條件。

因此可以維護 $nums[i+1]$ 中最大值和最小值的 index，並在枚舉 $j$ 時同時更新，更新後只需檢查 $[idx_{max}, j]$ 和 $[idx_{min},, j]$ 是否滿足條件即可。

複雜度分析

時間複雜度： $O(n)$ ，其中 $n$ 為陣列 $nums$ 的長度。
空間複雜度： $O(1)$ 。

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        n = len(nums)
        max_idx = min_idx = 0 # 維護最大值和最小值的 index
        for j in range(indexDifference, n): # 枚舉右指針
            i = j - indexDifference # 左指針，與右指針相差 indexDifference
            # 更新 max_idx, min_idx
            if nums[i] > nums[max_idx]:
                max_idx = i
            elif nums[i] < nums[min_idx]:
                min_idx = i
            # 檢查是否存在答案
            if nums[max_idx] - nums[j] >= valueDifference:
                return [max_idx, j]
            if nums[j] - nums[min_idx] >= valueDifference:
                return [min_idx, j]
        return [-1, -1]

class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        int n = nums.size(), max_idx = 0, min_idx = 0;
        for (int j = indexDifference; j < n; j++){ // 枚舉右指針
            int i = j - indexDifference; // 左指針，與右指針相差 indexDifference
            // 更新 max_idx, min_idx
            if (nums[i] > nums[max_idx]) max_idx = i;
            else if (nums[i] < nums[min_idx]) min_idx = i;
            // 檢查是否存在答案
            if (nums[max_idx] - nums[j] >= valueDifference) return {max_idx, j};
            else if (nums[j] - nums[min_idx] >= valueDifference) return {min_idx, j};
        }
        return {-1, -1};
    }
};