力扣(leetcode) 303. 区域和检索 - 数组不可变 (前缀和)
题目在这:
思路分析:
求i到j之间的元素之和。
这是一道前缀和的题目。 比如数组 [1,2,3] 则前缀和的数组 【1，3，6】 。前缀和数组第i个元素，为原数组的前i个数之和。 建立好前缀数组之后，直接从前缀数组返回即可。
完整代码
class NumArray:
def __init__(self, nums: List[int]):
n = len(nums)
self.prenum = [0] * (n + 1)
for i in range(n):
self.prenum[i + 1] = self.prenum[i] + nums[i]
def sumRange(self, left: int, right: int) -> int:
return self.prenum[right + 1] - self.prenum[left]
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)
这里一定要想清楚，建立的前缀和第0项为0，从第1项开始，为原数组的前1项和。 所以比如需要输出2到4之间的元素和， 则需要 原数组第2项、第3项、第4项的元素之和。则前缀和的第5项(原数组中第0项、第1项、第2项、第3项、第4项) 减去 前缀和第2项(原数组中第0项，第1项)。 显然，得到的是:原数组 第2项、第3项、第4项之和。
