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
}

原來題目主題的二分搜要這樣寫 感謝說明

大師