题目

难度：★☆☆☆☆
类型：数组

给定一个整数数组 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))

如有疑问或建议，欢迎评论区留言~