分割數組的方法數

2270。分割數組的方法數

難度：中

主題：陣列、前綴和

給你一個0索引長度為n的整數數組nums。

若符合以下條件，

nums 在索引 i 處包含 有效分割：

• 前 i 1 個元素的總和大於或等於後 n - i - 1 個元素的總和。
• i 右邊至少有一個 元素。即，0＜＝i＜1。 n - 1.

回傳

有效分割的數量，以nums為單位。

範例1：

• 輸入： nums = [10,4,-8,7]
• 輸出： 2
• 說明： 將 nums 拆分為兩個非空部分的方法有以下三種：
  在索引 0 處分割 nums。然後，第一部分是 [10]，其總和為 10。第二部分是 [4,-8,7]，其總和為 3。因為 10 >= 3 , i = 0 是有效的分割。
  在索引1處分割nums。然後，第一部分是[10,4]，其和是14。第二部分是[-8,7]，其和是-1。由於 14 >= -1，因此 i = 1 是有效的分割。
  在索引 2 處拆分 nums。然後，第一部分是 [10,4,-8]，其總和為 6。第二部分是 [7]，其總和為 7。因為 6
因此，nums 中的有效分割數為 2。

範例2：

• 輸入： nums = [2,3,1,0]
• 輸出： 2
• 解釋： nums 中有兩個有效的分割：
  在索引1處分割nums。然後，第一部分是[2,3]，其和是5。第二部分是[1,0]，其和是1。由於5 >= 1， i = 1 是有效的分割。
  在索引 2 處拆分 nums。然後，第一部分是 [2,3,1]，其和為 6。第二部分是 [0]，其和為 0。由於 6 >= 0， i = 2 是有效的分割。

約束：

2 5 -10
• 5 ⁵

提示：

對於任意索引 i，我們如何從前 i 個元素的總和中找到前 (i 1) 個元素的總和？
如果陣列的總和已知，我們如何檢查前（i 1）個元素的總和是否大於或等於其餘元素？

解：

我們可以透過以下步驟來實現它：

方法：

1. 前綴和：首先，我們從左邊計算陣列的累積和，這有助於檢查前 i 1 個元素的總和。
2. Total Sum：計算陣列的總和，這對於檢查剩餘元素的總和是否小於或等於前 i 1 個元素的總和很有用。
3. 迭代數組：對於每個有效索引 i（其中 0
4. 效率：不用重複重新計算總和，而是使用前綴總和與總和進行高效比較。

讓我們用 PHP 實作這個解：2270。分割數組的方法數

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

// Example usage:
$nums1 = [10, 4, -8, 7];
echo waysToSplitArray($nums1); // Output: 2

$nums2 = [2, 3, 1, 0];
echo waysToSplitArray($nums2); // Output: 2
?>

解釋：

1. $totalSum：此變數儲存nums陣列中所有元素的總和。
2. $prefixSum：此變數追蹤從左側開始（直到索引 i）的元素的累積和。
3. $remainingSum：這是從索引 i 1 到陣列末端的剩餘元素的總和。它是透過從 $totalSum 中減去 $prefixSum 來計算的。
4. 有效分割檢查：對於每個索引 i，我們檢查前綴總和是否大於或等於剩餘總和。

時間複雜度：

• O(n)：我們循環遍歷數組一次來計算總和，並再次檢查有效的分割。因此，時間複雜度與陣列的長度成線性關係。

空間複雜度：

• O(1)：我們只使用了一些額外的變數（$totalSum、$prefixSum、$remainingSum），因此空間複雜度是恆定的。

聯絡連結

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

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

• 領英
• GitHub

以上是分割數組的方法數的詳細內容。更多資訊請關注PHP中文網其他相關文章！