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
}