7-lines Python with prefix sums


  • 0
    B

    O(n * (upper-lower)) time complexity?

    class Solution(object):
        def countRangeSum(self, nums, lower, upper):
            psums, sum, count = {0:1}, 0, 0
            for num in nums:
                sum += num
                for x in range(sum-upper, sum-lower+1):
                    count += psums.get(x, 0)
                psums[sum] = psums.get(sum, 0)+1
            return count

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.