给定一个整数数组 nums
,求出数组从索引 i
到 j
(i ≤ j
)范围内元素的总和,包含 i
、j
两点。
实现 NumArray
类:
-
NumArray(int[] nums)
使用数组nums
初始化对象 -
int sumRange(int i, int j)
返回数组nums
从索引i
到j
(i ≤ j
)范围内元素的总和,包含i
、j
两点(也就是sum(nums[i], nums[i + 1], ... , nums[j])
)
思路
最开始想到的就是直接加,遍历求和就完事了,但是,题目给了一个对象,调用次数可能会比较多,这样的话,每次都遍历似乎不是个好方法,那么就有另外的一个方式,就是记录所有的数据和,然后根据输入直接返回对应的结果,但是这样,又会造成大量的空间的浪费(n*n)空间,于是,就又有了另外的思路,记录到i为止的所有的数据的和,然后,给定i,j,将对应的和求个差值,就能得到想要的结果了;
代码:
import itertools
from typing import List
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
# 获得到i为止的所有数字的和
self.acc = [a for a in itertools.accumulate(nums)]
def sumRange(self, i: int, j: int) -> int:
return self.acc[j] - self.acc[i] + self.nums[i]