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

题目描述

1.1、动态规划

class NumArray:

    def __init__(self, nums: List[int]):
        self.data = nums
        self.target = [] # target[i], 记录0~i的和
        sum_ = 0
        for i in range(len(nums)):
            sum_ += nums[i]
            self.target.append(sum_)
            
        

    def sumRange(self, i: int, j: int) -> int:
    	# i~j的和 为 target[j] - target[i] 在加上data[i]
        return self.target[j] - self.target[i] + self.data[i]