Re: [閒聊] 每日leetcode
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.214.143 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722757677.A.EFF.html
推
08/04 15:59,
1年前
, 1F
08/04 15:59, 1F
推
08/04 17:52,
1年前
, 2F
08/04 17:52, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 635 之 1550 篇)：