推荐几个的网站,网站建设辶金手指排名十五,云网站建站,wordpress queryposts难度#xff1a;Medium
题目#xff1a; 给你一个数组 nums #xff0c;它包含 n 个正整数。你需要计算所有非空连续子数组的和#xff0c;并将它们按升序排序#xff0c;得到一个新的包含 n * (n 1) / 2 个数字的数组。 请你返回在新数组中下标为 left 到 right #…难度Medium
题目 给你一个数组 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 Related Topics
数组双指针二分查找排序 重点解题思路
第一步 明确解题手段 根据题意来看是根据每个值向后模拟出一个前缀和。再分别看这几个模拟之后数组可以看出都是升序排序那么思路就很清晰了可以使用归并排序中的多路归并到一路的解法。 第二步 解题思路就是知道了使用多路归一路的解法那么就可以使用堆来解决每次添加每个升序数组的第一个值在小顶堆中进行操作直到找到left到right中的值 即可 源码讲解 class Solution { class Data { //自定义一个内部类辅助操作int i, j, val; //ij代表数组中的下标值val代表当前要模拟的值public Data(int i, int j, int val) {this.i i;this.j j;this.val val;}}public int rangeSum(int[] nums, int n, int left, int right) {PriorityQueueData p new PriorityQueue(new ComparatorData() {Overridepublic int compare(Data o1, Data o2) { //小顶堆排序规则return o1.val - o2.val;}});for (int i 0; i nums.length; i) p.offer(new Data(i, i, nums[i])); //把几个升序数组的头部添加进来int ans 0, mod (int) 1e9 7;for (int i 1; i right; i) { //一直poll到right的位置Data cur p.poll();if (i left) ans (ans cur.val) % mod; //如果目前下标符合left 那么就添加到结果集中if (cur.j 1 n) p.offer(new Data(cur.i, cur.j 1, cur.val nums[cur.j 1])); //如果目前下标还没有走到数组结尾那么就继续操作}return ans;}} 运行结果 如果您还有什么疑问或解答有问题可在下方评论我会及时回复。
系列持续更新中点个订阅吧喜欢练习算法那就点个攒吧
