Leetcode: 327. Count of Range Sum

Descrption

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note

A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

分析

最初的思路

1. 计算前缀和并用 bisect 加入到数组 presum[]
2. 使用 presum[] 计算 lower， upper 中的个数 。 此时计算的所有数据均是以 nums[0] 开头的数据。
    从 presum 中删除 nums[0] 数据， 并调整 lower 和 upper 的值 （这样 presum[] 数组中的数字就变相是 nums[1] 开头的前缀和）
3. 返回步骤 2 

结果是： 最初的版本超时，后续的版本做了一点点的优化。结果是只速度上只超过 8% 的提交

改进的思路

首先，个人认为最初的版本的代码的 时间复杂度是 nlogn。 不应该有这么差的表现。 一定有可以优化的地方，当时猜测 瓶颈是  从 presum[] 中删除 nums[i] 的这步操作。 
1. 先计算 nums 的总和, 并存储到 ssum
2. 从后往前迭代数据 , 即 range(N-1, -1, -1)。 根据 ssum 和 nums[i] 调整 lower 和 hi 的值。
    使用 bisect 搜索满足条件的个数。 将 nums[i] 加入到 presum[]
3. 返回步骤2

结果： 战胜 100 % 的提交

code

class Solution(object):
    def _do(self, nums, lower, hi):
        h, h2 = [] , []
        ans, ssum, N =0,  0, len(nums)
        for i, v in enumerate(nums):
            ssum += v
            bisect.insort(h2, ssum)
            bisect.insort(h, (ssum, i))
        # print(h)
        # print(h2)
        ssum = 0
        for i in range(N):
            hp = bisect.bisect_right(h2, hi)
            lw = bisect.bisect_left(h2, lower)
            # print(hp, lw, h, lower, hi)
            ssum += nums[i]
            # do sth
            hi += nums[i]
            lower += nums[i]
            ans += hp-lw
            ep1 = bisect.bisect_right(h, (ssum,i))
            if ep1 == len(h):
                ep1 -= 1
            while True:
                if h[ep1][1] == i:
                    h2 = h2[:ep1] + h2[ep1+1:]
                    h = h[:ep1] + h[ep1+1:]
                    break
                ep1 -= 1
        return ans

beat 8%

去除了 h2 的操作， 少一个数组需要维护
class Solution(object):
    def _do(self, nums, lower, hi):

        ans, ssum, N, h =0,  0, len(nums), []

        for i, v in enumerate(nums):
            ssum += v
            bisect.insort(h, ssum)

        # print(h)
        # print(h2)
        ssum = 0
        for i in range(N):
            hp = bisect.bisect_right(h, hi)
            lw = bisect.bisect_left(h, lower)
            # print(hp, lw, h, lower, hi)
            ssum += nums[i]
            # do sth
            hi += nums[i]
            lower += nums[i]
            ans += hp-lw
            ep1 = bisect.bisect_right(h, ssum)
            if ep1 == len(h):
                ep1 -= 1
            while True:
                if h[ep1] == ssum:
                    h = h[:ep1] + h[ep1+1:]
                    break
                ep1 -= 1
        return ans

beat 100 %

class Solution(object):
    def _do(self, nums, lower, hi):
        ans, ssum, N, =0,  sum(nums), len(nums)
        h = [ssum]
        
        for i in range(N-1, -1, -1):
            ssum -= nums[i]
            
            temp_lower, temp_upper = lower + ssum, hi + ssum
            ans += bisect.bisect_right(h, temp_upper) -  bisect.bisect_left(h, temp_lower)
            
            bisect.insort(h, ssum)
        return ans

总结

二分思想玩的不错～