長度為 K 的不同子數組的最大和

2461。長度為 K

的不同子數組的最大和

難度：中

主題：陣列、雜湊表、滑動視窗

給定一個整數數組 nums 和一個整數 k。求 nums 的所有子數組滿足以下條件的最大子數組和：

• 子數組的長度為k，且
• 子數組的所有元素不同。

傳回滿足條件的所有子數組的最大子數組和。如果沒有子數組滿足條件，則回傳0.

子數組是數組中連續的非空元素序列。

範例1：

• 輸入： nums = [1,5,4,2,9,9,9], k = 3
• 輸出： 15
• 解釋：長度為 3 的 nums 的子數組為：
  • [1,5,4]符合要求，總和為10。
  • [5,4,2]符合要求，總和為11。
  • [4,2,9]符合要求，總和為15。
  • [2,9,9]不符合要求，因為元素9重複。
  • [9,9,9]不符合要求，因為元素9重複。
  • 我們回傳 15，因為它是所有滿足條件子數組的最大子數組總和

範例2：

• 輸入： nums = [4,4,4], k = 3
• 輸出： 0
• 解釋：長度為 3 的 nums 的子數組為：
  • [4,4,4]不符合要求，因為元素4重複。
  • 我們回傳 0，因為沒有 子數組滿足條件。

約束：

• 1 5
• 1 5

提示：

1. 從以索引 i 結尾的大小為 k 的子數組移動到以索引 i 1 結尾的大小為 k 的子數組時，哪些元素會改變？
2. 只有兩個元素發生變化，i 1 處的元素被加到子數組中，i - k 1 處的元素從子數組中刪除。
3. 迭代大小為 k 的每個子數組，並追蹤子數組的總和以及每個元素的頻率。

解：

我們可以按照以下步驟操作：

方法：

1. 滑動窗口：窗口大小為k，我們在數組中滑動窗口，同時維護當前窗口的總和並檢查窗口中的所有元素是否不同。
2. 雜湊表（或關聯數組）：使用關聯數組（雜湊表）來追蹤目前視窗中元素的頻率。如果任何元素出現多次，則該視窗無效。
3. 更新視窗：當我們滑動視窗時，新增元素（即進入視窗的元素），並刪除舊元素（即離開視窗的元素）。相應地更新總和並檢查視窗是否有效（即所有元素都是不同的）。
4. 回傳最大和：我們需要追蹤有效子數組中遇到的最大和。

演算法:

1. 初始化一個雜湊表freq，用於儲存目前視窗中元素出現的頻率。
2. 先計算大小為 k 的第一個視窗的總和，如果視窗包含不同元素，則儲存結果。
3. 從左向右滑動視窗：
   • 刪除左側離開視窗的元素。
   • 加入從右側進入視窗的元素。
   • 更新總和和雜湊表，並檢查視窗是否仍只包含不同的元素。
4. 如果視窗具有有效的不同元素，則更新最大總和。
5. 如果沒有找到有效的子數組，則回傳0。

讓我們用 PHP 實作這個解：2461。長度為 K
的不同子數組的最大和

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

// Example usage:
$nums1 = [1,5,4,2,9,9,9];
$k1 = 3;
echo maximumSubarraySum($nums1, $k1); // Output: 15

$nums2 = [4,4,4];
$k2 = 3;
echo maximumSubarraySum($nums2, $k2); // Output: 0
?>

解釋：

1. 變數:

   • $maxSum：追蹤迄今為止找到的有效子數組的最大和。
   • $currentSum：儲存目前大小為k的滑動視窗的總和。
   • $freq：雜湊表（或關聯數組），儲存目前視窗中元素的頻率。

2. 滑動視窗:

   • 我們用循環遍歷數組。當我們移動視窗時，我們：
     • 將索引 $i 處的元素加到總和中並更新其頻率。
     • 如果視窗大小超過 k，我們從總和中刪除索引 $i - k 處的元素並降低其頻率。

3. 有效視窗檢查：

   • 一旦視窗大小達到 k（即，當 $i >= k - 1 時），我們透過確保頻率圖中不同鍵的數量等於 k 來檢查視窗中的所有元素是否不同。如果是，我們會更新最大總和。

4. 回傳結果:

   • 迭代數組後，我們返回找到的最大總和。如果沒有找到有效的子數組，maxSum 將保持為 0。

時間複雜度：

• O(n)，其中 n 是 nums 陣列的長度。每個元素在滑動視窗中新增和刪除一次，雜湊表操作（插入、刪除、檢查計數）平均為 O(1)。

空間複雜度：

• O(k) 為儲存目前視窗中元素出現頻率的雜湊表。

聯絡連結

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

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

• 領英
• GitHub

以上是長度為 K 的不同子數組的最大和的詳細內容。更多資訊請關注PHP中文網其他相關文章！