给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。
请你返回在新数组中下标为 **left 到 right （下标从 1 开始） 的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 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 复制代码
提示：
1 <= nums.length <= 10^3nums.length == n1 <= nums[i] <= 1001 <= left <= right <= n * (n + 1) / 2
暴力解
解题思路
暴力解也是最简单直接的思路，采用双层循环获取所有的子数组和值插入一个和值数组。
对和值数组进行升序排序。
获取区间中的子数组和值之和，并对 10^9 + 7 取模后返回即可。
代码实现
var rangeSum = function(nums, n, left, right) { // 初始化子数组和数组 const sums = [] // 双层遍历，获取所有子数组和 for(let i = 0;i<n;i++){ let sum = nums[i]; sums.push(sum); for(let j = i+1;j<n;j++){ sum += nums[j]; sums.push(sum) } } // 子数组和升序排序 sums.sort((a,b) => a-b) // 累加区间和 let res = 0; for(let i = left-1;i<right;i++){ res += sums[i] } // 返回区间和取模结果 return res%1000000007 }; 复制代码
小顶堆+多路归并
解题思路
首先我们看一下以 1,2,3,4 为例双层循环求所有子数组和的过程。
我们暴力解中的外层循环其实就是每一行的第一个元素，内层循环就是每一行的后续元素。
暴力解的效率低是因为不管我们要求的 left、right 区间是哪里，都会找到所有的子数组和，而且是无序的，还有对子数组和数组进行升序排序。
这里我们采用小顶堆+多路合并的技巧，实现只需要获取前 right 个元素，并且保证获取到的子数组和是从小到大的。
具体思路如下：
我们将上图每一行看做一路，初始的时候将每一路的第一个值插入小顶堆，那么此时堆顶就保存了其中的最小值。 接下来我们从 1-right 进行循环，循环过程中每次弹出堆顶元素，因为整体逻辑是多路合并且保存在小顶堆中，那么此时弹出的堆顶元素，必然是未处理元素中的最小值。如果此时循环处理 left-right 区间中，则结果值累加当前元素保存的子数组和值，并且根据当前元素，推导所在路的下一个子数组和，插入堆中。
这样每次用堆中的最小值推导所在路的下一个元素，就保证了每次弹出的堆顶元素都是未处理元素中的最小值，同时也可以获取到所有的子数组和。
最后当 i 大于 right 的时候，结果值中就存储了 left-right 区间中的子数组和的和值，将其对 10^9 + 7 取模后返回即可。
代码实现
var rangeSum = function(nums, n, left, right) { // 创建小顶堆实例 const heap = new Heap() // 首先将每一路的第一个值放入堆中 for(let i = 0; i < n; i++) heap.push({i,j:i,sum:nums[i]}) // 初始化结果值 let res = 0 // 从 1-right 遍历，获取前 right 个子数组和值 for(let i = 1; i <= right; i++) { // 获取当前未处理的子数组和值的最小值 const min = heap.pop() // 如果当前处于 left-right 区间，则累加结果值 if(i >= left) res += min.sum // 根据当前元素，推导所在路的下一个元素，插入堆中 if(min.j<n-1) heap.push({i:min.i, j:min.j + 1, sum:min.sum + nums[min.j + 1]}) } // 返回结果 return res%1000000007 }; // 小顶堆 class Heap { constructor() { // 初始化数组和size this.arr = []; this.size = 0; } // 插入操作 push(item) { this.arr.push(item); this.size++; // 插入后的自下向上平衡调整 if(this.size>1){ let cur = this.size-1, parent = (cur-1)>>1; while(cur>0 && this.arr[parent].sum>this.arr[cur].sum){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } } } // 弹出操作 pop() { // 特殊处理弹出最后一个元素 if(this.arr.length===1){ this.size--; return this.arr.pop() } const res = this.arr[0]; this.arr[0] = this.arr.pop(); this.size--; // 弹出后的自上向下平衡调整 let cur = 0,childl = 1,childr = 2; while( (childl<this.size && this.arr[childl].sum<this.arr[cur].sum) || (childr<this.size && this.arr[childr].sum<this.arr[cur].sum) ){ if(childr<this.size && this.arr[childr].sum<this.arr[childl].sum){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl } childl = cur*2+1,childr = cur*2+2; } return res; } } 复制代码
至此我们就完成了 leetcode-1508-子数组和排序后的区间和
如有任何问题或建议，欢迎留言讨论！
