已排序子數組和的範圍和

1508。排序子數組和的範圍和

中

給定一個由 n 個正整數組成的陣列 nums。您計算了數組中所有非空連續子數組的總和，然後按非降序對它們進行排序，創建了一個包含 n * (n + 1) / 2 個數字的新數組。

傳回新數組中從左到右索引（從1開始索引）的數字總和。由於答案可能是一個巨大的數字，因此返回它模 109 ^{+ 7.}

範例1：

• 輸入： nums = [1,2,3,4], n = 4, left = 1, right = 5
• 輸出： 13
• 解釋： 所有子數組的和均為 1, 3, 6, 10, 2, 5, 9, 3, 7, 4。將它們依非降序排序後，我們得到新陣列 [1, 2, 3、3、4、5、6、7、9、10]。從索引 le = 1 到 ri = 5 的數字和為 1 + 2 + 3 + 3 + 4 = 13。

範例2：

• 輸入： nums = [1,2,3,4], n = 4, left = 3, right = 4
• 輸出： 6
• 解釋： 給定的陣列與範例 1 相同。我們有新數組 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]。從索引 le = 3 到 ri = 4 的數字和為 3 + 3 = 6。

範例 3：

• 輸入： nums = [1,2,3,4], n = 4, left = 1, right = 10
• 輸出： 50

約束：

n == nums.length
1 1 1

提示：

計算所有總和並將其保存在陣列中。
然後由左至右索引並計算答案模 1e9 + 7。

解：

要解決這個問題，我們可以按照以下步驟操作：

產生非空連續子數組的所有可能的和。
對結果陣列進行排序。
計算從左到右索引（從1開始）的元素總和。
傳回對 10 取模的結果
4. 9 ^{+ 7.}

讓我們用 PHP 實作這個解：

1508。已排序子數組和的範圍和

<?php
// Example usage
$nums = array(1, 2, 3, 4);
$n = 4;
$left = 1;
$right = 5;

echo rangeSum($nums, $n, $left, $right); // Output: 13

$left = 3;
$right = 4;
echo rangeSum($nums, $n, $left, $right); // Output: 6

$left = 1;
$right = 10;
echo rangeSum($nums, $n, $left, $right); // Output: 50

?>

解釋：

1. 生成子數組和：

   迭代子數組的每個起始索引 i。
   對於每個起始索引 i，計算以索引 j 結尾的子數組總和（其中 j >= i）。
   將每個計算出的子數組總和附加到 $sums 數組。

2. 將總和排序：

   使用 PHP 的 sort() 函數對 $sums 陣列進行非降序排序。

3. 求和所需範圍：

   從 left-1 索引迭代到 right-1 索引（因為問題使用基於 1 的索引）。
   累積此範圍內的元素總和，注意使用模 10
   • 9 ^{+ 7 以避免溢位。}

此解決方案有效地產生所有子數組總和，並對它們進行排序，並根據指定計算所需的範圍總和。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給

存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

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

• 領英
• GitHub

以上是已排序子數組和的範圍和的詳細內容。更多資訊請關注PHP中文網其他相關文章！