Share my Python solution, O(n) for init and O(1) for query


  • 1
    D

    Use an extra element for summation so we don't need to check boundary condition in the query.

    class NumArray(object):
        def __init__(self, nums):
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            self.sums = [0] * (len(nums) + 1)
            for i in xrange(len(nums)):
                self.sums[i+1] = self.sums[i] + nums[i]
    
        def sumRange(self, i, j):
            """
            sum of elements nums[i..j], inclusive.
            :type i: int
            :type j: int
            :rtype: int
            """
            return self.sums[j+1] - self.sums[i]

  • 0
    T
    This post is deleted!

Log in to reply
 

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