Re: [閒聊] 每日leetcode

[dont (dont)]

1508. Range Sum of Sorted Subarray Sums

## 思路

建heap 存range_sum 跟 idx
每次pop出來的值再加上nums[idx+1]丟回去heap
然後加總left~right次pop的range sum

## Complexity

Time: O(max(N, right) log N) = O(N^2 logN)
Space: O(N)

```python
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        MOD = 1_000_000_007

        # O(N)
        pq = [(num, idx) for idx, num in enumerate(nums)]  # (num, idx)
        heapq.heapify(pq)

        # O(max(N, right) log N)
        ans = 0
        for i in range(1, right+1):
            num, idx = heapq.heappop(pq)
            if i >= left:
                ans = (ans + num) % MOD
            if idx + 1 < n:
                heapq.heappush(pq, (num + nums[idx+1], idx+1))

        return ans
```

--
http://i.imgur.com/OLvBn3b.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.182 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722744751.A.CC8.html
推 sustainer123: 大師