题目
难度：★☆☆☆☆
类型：数组
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
示例
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
解答
正常情况下，我们的思路是这样的：
class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return sum(self.nums[i:j + 1])
这种办法提交可以跑通，但是耗时很长。如果我们注意到了“说明”中的提示，就可以考虑使用一种记忆化的方式，以避免如上大量重复计算。
这里，我们在实例化数组类（NumArray）时，就对输入数组nums进行处理，我们准备一个新的数组sums，用于存储到输入数组某一位置为止之前的所有数的和，即：
sums[i] = sum(nums[0:i+1]), (0 <= i <= i+1, nums[0]=0)
因此sums数组的长度要比nums大1
我们想要求出从nums中从i到j（包括j）在内的所有数的和，通过sums中两个元素相减即可轻易获得：
sum(nums[i:j+1]) = sums[j+1] - sum[i]
编码实现如下：
class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
# self.nums = nums
self.sums = []
cur_sum = 0
self.sums.append(cur_sum) # 加入第0个数
for num in nums: # 遍历数组中每个数
cur_sum += num # 到当前为止的数组和
self.sums.append(cur_sum) # 添加到列表中
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return self.sums[j+1] - self.sums[i] # 返回下标为j+1与下标为i的差值即可
if __name__ == "__main__":
# 测试一下
n = NumArray([-2, 0, 3, -5, 2, -1])
print(n.sumRange(0, 2))
print(n.sumRange(2, 5))
print(n.sumRange(0, 5))
如有疑问或建议，欢迎评论区留言~
