class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
self.nums = nums
def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
sum = 0
for k in range(i,j+1):
sum += self.nums[k]
return sum
# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.sumRange(1, 2)
I do not understand why a legitimate O(n) solution is not accepted.


Never mind. I understood the reason why they needed to optimize. Multiple calls to my previous method would have been O(n) each.
class NumArray(object): def __init__(self, nums): """ initialize your data structure here. :type nums: List[int] """ sumArr = [0] * len(nums) if len(nums) > 0: sumArr[0] = nums[0] for i in range(1,len(nums)): sumArr[i] = nums[i] + sumArr[i1] self.sum = sumArr def sumRange(self, i, j): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ if i == 0: return self.sum[j] else: return self.sum[j]  self.sum[i1] # Your NumArray object will be instantiated and called as such: # numArray = NumArray(nums) # numArray.sumRange(0, 1) # numArray.sumRange(1, 2)