已排序子数组和的范围和

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中文网其他相关文章！