1508. Range Sum of Sorted Subarray Sums

题目信息

题号:

1508

难度:

Medium

主题:

数组、连续子数组、排序、前缀和

原题:

LeetCode 1508

重点:

枚举所有非空连续子数组的和并排序,求一基下标区间 [left,right] 的总和并取模

题目重述

给定长度为 n 的正整数数组 nums。计算其所有非空连续子数组的元素和,共有 n * (n + 1) / 2 个,并将这些和按非递减顺序排列。

请返回排序后第 left 项到第 right 项的总和,位置从 1 开始计数。结果对 10^9 + 7 取模。

1 <= n == nums.length <= 1000,1 <= nums[i] <= 100,1 <= left <= right <= n * (n + 1) / 2。

自建示例

区间可以跨越重复的子数组和:

输入:nums = [1,2,3], n = 3, left = 2, right = 5
输出:13
解释:全部子数组和排序后为 [1,2,3,3,5,6],第 2 至 5 项之和为 2+3+3+5=13。

单元素数组只有一个子数组和:

输入:nums = [7], n = 1, left = 1, right = 1
输出:7
解释:唯一非空连续子数组就是整个数组。