1508. Range Sum of Sorted Subarray Sums¶
题目信息¶
- 题号:
1508
- 难度:
Medium
- 主题:
数组、连续子数组、排序、前缀和
- 原题:
- 重点:
枚举所有非空连续子数组的和并排序,求一基下标区间
[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
解释:唯一非空连续子数组就是整个数组。