Python simple solution. O(n) time DP


  • -2
    H
    class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        length = len(nums)
        self.dic = {}
        self.dic[(0,-1)]=0 ## sumRange(i,j), in case i==0
        for j in range(length):
                if j != 0:
                    self.dic[(0,j)] = self.dic[(0,j-1)] + nums[j]
                else:
                    self.dic[(0,j)] = nums[j]
    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.dic[(0,j)]-self.dic[(0,i-1)]

Log in to reply
 

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