【题目描述】
【代码思路】简单动态规划,由于两个限制,数组不可变和会多次调用sumRange函数,需要新建一个数组去保存和。
【上代码】
class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.sum_list=[0]
for i in range(len(nums)-1,-1,-1):
self.sum_list.insert(0,nums[i]+self.sum_list[0])
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return self.sum_list[i]-self.sum_list[j+1]
看效果,时间复杂度是线性的: