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]
的範圍內。
(copy[i] - copy[i - 1]) == (original[i] - original[i - 1])
for1 <= i <= n - 1
.lower[i] <= original[i] <= upper[i]
for0 <= i <= n - 1
.
解題思維
這題的關鍵在於理解 copy
陣列是由 original
陣列加上一個整數 k
所得到的結果。因此,我們可以將問題轉化為尋找一個整數 k
,使得對於每個 i
,original[i] = copy[i] - k
都滿足 bounds[i][0] <= original[i] <= bounds[i][1]
。
所以簡單來,我們是要找出 k
的上下界。
程式碼
1 | class Solution: |