LeetCode 筆記 - 3468. Find the Number of Copy Arrays

題目在此 3468. Find the Number of Copy Arrays

給定一個整數陣列 nums 與 bounds, 其中 $bounds[i] = [lower_i, upper_i]$，請找出有多少個不同的整數陣列 original 可以經過某個整數 k 的加法運算後，變成 nums，且每個 original[i] 都在 bounds[i] 的範圍內。

1. (copy[i] - copy[i - 1]) == (original[i] - original[i - 1]) for 1 <= i <= n - 1.
2. lower[i] <= original[i] <= upper[i] for 0 <= i <= n - 1.

解題思維

這題的關鍵在於理解 copy 陣列是由 original 陣列加上一個整數 k 所得到的結果。因此，我們可以將問題轉化為尋找一個整數 k，使得對於每個 i，original[i] = copy[i] - k 都滿足 bounds[i][0] <= original[i] <= bounds[i][1]。

所以簡單來，我們是要找出 k 的上下界。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def countArrays(self, original: List[int], bounds: List[List[int]]) -> int:

        max_b = inf
        min_b = -inf

        for i in range(len(original)):
            max_b = min(max_b, bounds[i][1] - original[i])
            min_b = max(min_b, bounds[i][0] - original[i])

        if max_b >= min_b:
            return max_b - min_b + 1
        return 0

也許你也會想看看

• LeetCode 筆記 - 349. Intersection of Two Arrays
• LeetCode 筆記 - 189. Rotate Array
• LeetCode 筆記 - 1480. Running Sum of 1d Array