327.md

327 Count of Range Sum

Description

link

---

Solution

• We add current num to sm in each iteration and store previous sorted sums in "sums" array.
• For getting proper range in "sums" array for current sm, we check critical points sm - lower and sm - upper.
• Imagine i and j are the two points on "sums" array that we get such as i <= j:
  • In this case, sums[i] <= sums[j].
  • As a result, we get index i from sm - upper and index j from sm - lower due to the fact that sm -lower <= sm - upper.
  • As a reminder, there could be duplicates in "sums" array so we should get leftmost i and rightmost j.
  • Add i - j to result and insert current sm in "sums" array
  • return result

高票回答里有用红黑树做的也有用merge sort做的，但是在python里面可以利用先天自带的bisect库来做BST这样一个过程，思路如下：

• 遍历数组
• 过程中记录下来每一个到当前状况下的总和（求区域和的问题必须要有一个总和数组）
• 利用当前总和减去lower和upper就是需要在sums这个已经排好序的总和数组当中找到的下标，中间这一段均满足条件，加到答案当中去
• 将当前总和加入到sums当中，当然也是利用insort函数

---

Code

O(nlog(n))

class Solution:
    def countRangeSum(self, nums: 'List[int]', lower: 'int', upper: 'int') -> 'int':
        sums, sm, res = [0], 0, 0
        for num in nums:
            sm += num
            res += bisect.bisect_right(sums, sm - lower) - bisect.bisect_left(sums, sm - upper)
            bisect.insort(sums, sm)
        return res