題目資訊

• 題目編號: 2145
• 題目連結: Count the Hidden Sequences
• 主題: Array, Prefix Sum

題目敘述

你有一個0-索引的整數陣列 n，名為 differences，描述了一個隱藏序列的長度 $(n + 1)$ 中，每一對連續整數之間的差異。更正式來說，稱這個隱藏序列為 hidden，則有 $\text{differences}[i] = \text{hidden}[i + 1] - \text{hidden}[i]$。

你還得到兩個整數 lower 和 upper，這描述了一個範圍 $[ \text{lower}, \text{upper} ]$，此範圍內的值是隱藏序列可以包含的。

• 例如，給定 differences = [1, -3, 4]，lower = 1，upper = 6，隱藏序列是一個長度為 4 的序列，其元素介於 1 和 6 (含)。

  • [3, 4, 1, 5] 和 [4, 5, 2, 6] 是可能的隱藏序列。
  • [5, 6, 3, 7] 不可能，因為它包含一個大於 6 的元素。
  • [1, 2, 3, 4] 不可能，因為差異不正確。

返回有多少個可能的隱藏序列。如果沒有可能的序列，返回 0。

範例 1:

輸入: differences = [1,-3,4], lower = 1, upper = 6
輸出: 2
解釋: 可能的隱藏序列是:
- [3, 4, 1, 5]
- [4, 5, 2, 6]
因此，我們返回 2。

範例 2:

輸入: differences = [3,-4,5,1,-2], lower = -4, upper = 5
輸出: 4
解釋: 可能的隱藏序列是:
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
因此，我們返回 4。

範例 3:

輸入: differences = [4,-7,2], lower = 3, upper = 6
輸出: 0
解釋: 沒有可能的隱藏序列。因此，我們返回 0。

約束條件:

• $n == \text{differences.length}$
• $1 \leq n \leq 10^5$
• $-10^5 \leq \text{differences}[i] \leq 10^5$
• $-10^5 \leq \text{lower} \leq \text{upper} \leq 10^5$

直覺

此問題可以理解為根據給定的連續元素之間的差異累積和來重建一個數字序列。任務是找出在定義的數字範圍內有多少種可能的此類序列。直覺上，我們需要確定隱藏序列的有效起始值範圍，以便在累積應用差異時，整個序列保持在定義的界限內。

解法

解決此問題的方法涉及使用提供的差異模擬序列重建過程，以建立隱藏序列的潛在範圍。以下是逐步的解釋：

1. 初始化變量：我們首先設定 current_value、max_value 和 min_value 為 0。這些將用來追踪在遍歷 differences 陣列時累積和的變化。

2. 迭代並計算累積和：當我們遍歷 differences 陣列中的每個 difference 時，我們通過將每個 difference 加到 current_value 來更新 current_value。此累積和模擬了隱藏序列中一個元素到下一個元素的轉變。

3. 追踪極值：在迭代過程中，我們不斷更新 max_value 為自身與 current_value 的最大值，同樣地，min_value 為自身與 current_value 的最小值。這使我們能夠捕捉從初始起點的最大正偏移和最大負偏移。

4. 計算可能的起始點：隱藏序列的初始值 hidden[0] 的可能範圍可以從約束條件 lower 和 upper 中推導出來。具體來說，當序列中的每個值都在包含範圍 $[ \text{lower}, \text{upper} ]$ 內時，序列是有效的。因此，通過以下公式可以確定有效起始值的數量：
   $$ \text{number of valid sequences} = \max(\text{upper} - \text{lower} - \text{max\_value} + \text{min\_value} + 1, 0) $$

5. 返回結果：如果計算得出一個正的範圍，則返回該數字作為有效起始點的計數；否則返回 0，表示沒有可能的有效序列。

此演算法有效地捕捉了序列在給定界限內的潛在偏移範圍，並通過評估得出的範圍條件有效地確定了有效序列的數量。使用簡單的算術運算和極值追踪來優化解決方案，以滿足對於大型輸入尺寸的約束。

程式碼

C++

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        // 初始化當前值、最大值和最小值來追蹤序列範圍
        long long current_value = 0;
        long long max_value = 0;
        long long min_value = 0;

        // 計算差異的累加和以找到範圍
        for (int difference : differences) {
            current_value += difference;
            max_value = max(max_value, current_value);
            min_value = min(min_value, current_value);
        }

        // 使用導出的範圍計算可能的序列數量
        return max(int(upper - lower - max_value + min_value + 1), 0);
    }
};

Python

class Solution:
    def numberOfArrays(self, differences, lower, upper):
        # 初始化當前值、最大值和最小值以追蹤序列的界限
        current_value = 0
        max_value = 0
        min_value = 0

        # 計算差異的累積總和以找到界限
        for difference in differences:
            current_value += difference
            max_value = max(max_value, current_value)
            min_value = min(min_value, current_value)

        # 使用推導出的界限計算可能序列的數量
        return max(int(upper - lower - max_value + min_value + 1), 0)

複雜度分析

• 時間複雜度: $O(n)$
  該函數對 differences 陣列進行一次迭代，對每個元素執行常數時間操作（加法、比較）。因此，時間複雜度與輸入陣列的大小 $n$ 成線性關係。因此，時間複雜度為 $O(n)$。
• 空間複雜度: $O(1)$
  該函數使用固定數量的額外空間來儲存像 current_value、max_value 和 min_value 等變數。這些變數佔據的空間量與輸入陣列的大小無關，是常數。因此，空間複雜度為 $O(1)$。