从Leetcode 每日一题练习继续讨论：
1508. 子数组和排序后的区间和
1508. Range Sum of Sorted Subarray Sums
题解
本题先考虑计算子数组的和时, 如果固定子数组的开始下标, 不断扩展子数组的长度, 则这些子数组的和具有天然的递增顺序. 即可以通过固定子数组的开始下标得到以某下标开始的子数组和的递增序列. 遍历到以下一个数组下标开始的子数组并计算子数组和时, 相当于合并两个递增的数组, 将和不断插入到之前已经有序的数组中, 为了快速插入到之前的有序数组并且保持数组仍为有序数组, 可以使用优先级队列.
代码
type Pq []int
func (pq Pq)Len() int{
return len(pq)
}
func (pq Pq) Less(i, j int)bool{
return pq[i] < pq[j]
}
func (pq Pq) Swap(i, j int){
pq[i],pq[j] = pq[j],pq[i]
}
func (pq *Pq) Pop() interface{} {
n := len(*pq)
item := (*pq)[n-1]
(*pq) = (*pq)[0:n-1]
return item
}
func (pq *Pq) Push(x interface{}) {
*pq = append(*pq, x.(int))
}
func rangeSum(nums []int, n int, left int, right int) int {
pq := Pq{}
sum := 0
for j:=0;j<n;j++{
sum += nums[j]
pq = append(pq, sum)
}
heap.Init(&pq)
for i:=1;i<n;i++{
sum = 0
for j:=i;j<n;j++{
sum += nums[j]
heap.Push(&pq, sum)
}
}
for i:=1;i<left;i++{
heap.Pop(&pq)
}
result := 0
for left<=right{
result += heap.Pop(&pq).(int)
left++
}
return result % (1000000007)
}
总结
这种解法时间复杂度很高, 可以使用前缀和的前缀和求解, 这种思路比较复杂, 推荐看官方题解