Python O(n) Solution with clear explanation


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

    The strategy is simple. We use a new list numsSum to store the accumulated numbers based on the given nums list. Then numsSum[j] - numsSum[i] + nums[i] is the range sum form i to j inclusive.


Log in to reply
 

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