leetcode-303. 区域和检索 - 数组不可变

https://leetcode-cn.com/problems/range-sum-query-immutable/

第一遍看完题目，没看懂考点在哪里。

按照理解写下代码，竟然通过了

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, i: int, j: int) -> int:
        s = 0
        for x in range(i, j+1):
            s += self.nums[x]
        return s

避免重复计算，对第 i 个元素，sums[i] 存储 nums[0] + ... + nums[i]

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.sums = {}
        self.sums[-1] = 0
        for i in range(0, len(nums)):
            self.sums[i] = self.sums[i-1] + nums[i]

    def sumRange(self, i: int, j: int) -> int:
        return self.sums[j] - self.sums[i-1]

meishaoming / blog

leetcode-303. 区域和检索 - 数组不可变 #83