※ 引述《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)