Leetcode 1508. Range Sum of Sorted Subarray Sums（暴力解法与优化解法，含详细解析）

Leetcode 1508. Range Sum of Sorted Subarray Sums

题目链接： Range Sum of Sorted Subarray Sums

难度：Medium

题目大意：

输入一组正数，取连续的若干个数组成子数组，对所有的子数组求和，得到的子数组之和组成一个新的数组，对该数组的区间[left-1,right-1]求和。

思路：

思路1：

暴力解法，把所有的子数组的和求出来，组成一个新的数组，然后对数组进行排序，再对某个区间求和。

思路2（参考高赞回答）：

因为所有数都是正数，所以以某个数作为起点，子数组包含的数越多，子数组之和也越大。利用这个性质来解题。找出最小的right个子数组的和即可，不用求出所有子数组的和。这种方法要比思路1快很多。
比如数组[1,2,3,4],分别以各个数作为子数组的起点，找出前right个最小的子数组的和，要用优先队列来存储各个子数组的和以及子数组中最后一个元素在原数组中的下标，刚开始是每个子数组只有一个数，弹出和最小的子数组，将该子数组加上后面一个数，然后再弹出和最小的子数组，直到找到题目要求区间内的所有子数组之和。

题目要找的是子数组的和，所以不用记录子数组个各个元素，记录子数组的和以及子数组最后一个元素在原数组中的下标即可。

代码

思路1：

class Solution {public int rangeSum(int[] nums, int n, int left, int right) {List<Long> sums=new ArrayList<>();long sum,mod=1000000007;for(int i=0;i<n;i++){for(int j=i;j<n;j++){sum=0;for(int k=i;k<=j;k++){sum+=nums[k];}sums.add(sum);}}Collections.sort(sums);left--;right--;long total=0;for(int i=left;i<=right;i++){total=(total%mod+sums.get(i)%mod)%mod;}return (int)total;}
}

思路2：

class Solution {public int rangeSum(int[] nums, int n, int left, int right) {int len=nums.length;Queue<int []>pq=new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);for(int i=0;i<len;i++){pq.offer(new int[]{nums[i],i+1});//第一个数表示子数组的和，第二个数表示加到原数组的第几个元素。}int ans=0,mod=1000000007;int index;for(int i=1;i<=right;i++){//找出子数组和最小的前right个子数组的和int[] p=pq.poll();if(i>=left){ans=(ans%mod+p[0]%mod)%mod;}if(p[1]<n){//如果子数组还没加到nums的第n个元素index=p[1];p[0]+=nums[index];//数组nums下标从0开始p[1]++;pq.offer(p);//重新加入PriorityQueue}}return ans;}
}