Solution to LeetCode 303 Range Sum Query - Immutable.
LeetCode 303
Range Sum Query - Immutable (Easy) [link]
1] Brute Force
Time complexity O(n^2).
2] Dynamic Programming
sum[0,i] = sum[0,i-1] + num[i]
sum[j,i] = sum[0,i] - sum[0,j-1]
Time complexity O(n). Space complexity O(n).
class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
self.SUM = [0] * len(nums)
self.SUM[0] = self.nums[0]
for i in range(1, len(self.nums)):
self.SUM[i] = self.SUM[i-1] + self.nums[i]
def sumRange(self, left, right):
"""
:type left: int
:type right: int
:rtype: int
"""
if left == 0: return self.SUM[right]
return self.SUM[right] - self.SUM[left-1]
