※ 引述《JIWP (神楽めあ的钱包)》之铭言：
: 1508. Range Sum of Sorted Subarray Sums
: 给一个矩阵
: 将所有的subarray的总和依照大小排序
: 回传index 第left到第right subarray的总和
: left、right是从1开始算，而不是0
: 思路:
: 最简单就是把所有可能列出来后进行排序
: 不然可以用binary search
: 按照题目限制subarray最大的总和在100000
: 就从0、100000进行二分法
: 每次去找总和小于等于middle的subarray有几个且这些subarray加起来是多少
: 最后就回传binarysearch(right)-binarysearch(left-1)就好了
: golang code :
: func rangeSum(nums []int, n int, left int, right int) int {
: CalSum := func(num int) (int, int) {
: cursum, totalsum := 0, 0
: cnt, minus := 0, 0
: j := 0
: for i := 0; i < n; i++ {
: for j < n && cursum+nums[j] <= num {
: cursum += nums[j]
: minus += nums[j] * j
: j++
: }
: cnt += j - i
: totalsum += cursum*j - minus
: minus -= nums[i] * i
: cursum -= nums[i]
: }
: return cnt, totalsum
: }
: bs := func(num int) int {
: l, r := 0, 100000
: cnt, sum := 0, 0
: for r > l {
: m := (r-l)/2 + l
: if c, s := CalSum(m); c <= num {
: l = m + 1
: cnt=c
: sum=s
: } else {
: r = m
: }
: }
: //[sum1 sum2 sum3 sum4]
: //[num num num num+i]
: //如上面会有多个sum可以得到总和比sum少的subarray有num个
: //这个二分法是在找sum4，subarray个数比num多的第一个
: //最后把这些subarray的总和-i*sum4就可以回传了
: return sum - (cnt-num)*l
: }
: return (bs(right) - bs(left-1)) % 1000000007
: }
:
思路:
早上没看清楚题目
以为要找所有子集合的和
看到连续子集合就end了
两个循环找到所有连续子集合的和
排序 加总 end
Python Code:
class Solution:
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
record = []
for i in range(n):
state = 0
for j in range(i,n):
state += nums[j]
record.append(state)
record.sort()
return sum(record[left-1:right])%(10**9+7)