。總和至少為 K 的最短子數組

862。總和至少 K 的最短子數組

難度：難

主題：陣列、二分查找、佇列、滑動視窗、堆疊（優先權佇列）、前綴和、單調佇列

給定一個整數數組 nums 和一個整數 k，傳回 總和至少為 k 的 nums 的最短非空子數組的長度。如果不存在這樣的子數組，則回傳-1.

子數組是數組的連續部分。

範例1：

• 輸入： nums = [1], k = 1
• 輸出： 1

範例2：

• 輸入： nums = [1,2], k = 4
• 輸出： -1

範例 3：

• 輸入： nums = [2,-1,2], k = 3
• 輸出： 3

約束：

• 1 5
• -10⁵ 5
• 1 9

解：

我們需要使用滑動視窗方法結合前綴和和單調隊列。以下是逐步方法：

步驟：

1. 字首和：

   • 首先，計算前綴和數組，其中索引 i 處的每個元素表示從數組開頭到 i 的元素總和。前綴 sum 允許我們在常數時間內計算任何子數組的總和。

2. 單調隊列：

   • 我們使用 deque（雙端佇列）來維護 prefix_sum 陣列的索引。雙端佇列將以前綴和的遞增順序進行維護。
   • 這可以幫助我們透過比較當前前綴和與較早的前綴和來有效地找到總和大於或等於 k 的子數組。

3. 滑動視窗邏輯：

   • 對於每個索引 i，檢查當前前綴和與任何先前前綴和（儲存在雙端佇列中）之間的差異是否大於或等於 k。
   • 如果是這樣，計算子數組的長度並根據需要更新最小長度。

演算法:

1. 初始化大小為 n 1 的 prefix_sum 陣列（其中 n 是輸入陣列的長度）。第一個元素為 0，因為零個元素的總和為 0。
2. 使用雙端佇列來儲存 prefix_sum 值的索引。雙端佇列將有助於有效率地找到滿足條件的最短子數組。
3. 對於陣列中的每個元素，更新 prefix_sum，並檢查雙端佇列以找到 sum 大於或等於 k 的最小子陣列。

讓我們用 PHP 實作這個解：862。總和至少 K 的最短子數組

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function shortestSubarray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1];
$k1 = 1;
echo shortestSubarray($nums1, $k1) . "\n"; // Output: 1

$nums2 = [1, 2];
$k2 = 4;
echo shortestSubarray($nums2, $k2) . "\n"; // Output: -1

$nums3 = [2, -1, 2];
$k3 = 3;
echo shortestSubarray($nums3, $k3) . "\n"; // Output: 3
?>

解釋：

1. 前綴與陣列：

   • 我們計算 prefix_sum 陣列中陣列的累積和。這有助於使用公式 prefix_sum[j 1] - prefix_sum[i].
   計算任何子數組 nums[i...j] 的總和

2. 單調隊列：

   • 雙端佇列以值的遞增順序保存 prefix_sum 陣列的索引。我們保持這個順序，以便我們可以有效地找到總和大於或等於 k 的最小子數組。

3. 滑動視窗邏輯：

   • 當我們遍歷 prefix_sum 陣列時，我們嘗試使用目前 prefix_sum[i] 和先前的 prefix_sum[deque[0]] 之間的差異來找出最小子陣列。
   • 如果差值大於或等於 k，我們計算子數組長度並更新找到的最小長度。

4. 回傳結果：

   • 如果沒有找到有效的子數組，則傳回-1。否則，傳回最小子數組長度。

時間複雜度：

• 時間複雜度： O(n)，其中 n 是輸入陣列的長度。每個元素最多被處理兩次（新增到雙端佇列時一次，刪除時一次）。
• 空間複雜度： O(n)，由於 prefix_sum 陣列和用於儲存索引的雙端佇列。

這種方法確保即使對於大量輸入，解決方案也能有效運作。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。總和至少為 K 的最短子數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！