v1
- 主要思路是最连续区间的列表进行切片在求累积。代码通过，但是耗时很长，多次计算，每次都要重新计算值，调用次数为n，那么计算的时间复杂度就是O(n)
class NumArray:
def __init__(self, nums: List[int]):
if len(nums) <= 0:
return None
self.numArray = nums
self.maxElement = 10**5
self.minElement = -10**5
self.maxCount = 10**4
self.counter = 1
def sumRange(self, i: int, j: int) -> int:
numsLength = len(self.numArray)
sumNum = 0
if self.counter > self.maxCount:
return None
if i < 0 or i >= numsLength:
return None
elif j < i or j >= numsLength:
return None
elif self.numArray[i] >= self.maxElement or self.numArray[i] <= self.minElement:
return None
else:
numC = self.numArray[i:j+1]
for i in numC:
sumNum += i
self.counter += 1
return sumNum
v2
- 看题解按缓存方法，将计算结果保存在字典中，如果字典中不存在，则计算结果，如果存在则直接取结果，时间复杂度最好为O(1)，空间复杂度为O(n)
allRet = {}
class NumArray:
def __init__(self, nums: List[int]):
if len(nums) <= 0:
return None
self.numArray = nums
self.maxElement = 10**5
self.minElement = -10**5
self.maxCount = 10**4
self.counter = 1
self.numsKey = tuple(self.numArray)
allRet[self.numsKey] = {}
def sumRange(self, i: int, j: int) -> int:
numsLength = len(self.numArray)
sumNum = 0
if self.counter > self.maxCount:
return None
if i < 0 or i >= numsLength:
return None
elif j < i or j >= numsLength:
return None
elif self.numArray[i] >= self.maxElement or self.numArray[i] <= self.minElement:
return None
else:
dicKey = tuple([i,j])
if not allRet.get(self.numsKey, None).get(dicKey, None):
sumNum = sum(self.numArray[i:j+1])
retDic = {
dicKey: sumNum
}
allRet[self.numsKey].update(retDic)
self.counter += 1
return sumNum
else:
self.counter += 1
return allRet.get(self.numsKey).get(dicKey)
v3
- 预处理累积的结果存放于列表中，每次取结果的时间复杂度为O(1)，空间复杂度为len(nums)+1 ，O(n)
- 按照测试用例的输入列表[-2, 0, 3, -5, 2, -1]，计算出每一个元素与前面所有元素的和 [0, -2, -2, 1, -4, -2, -3]，由于题目要求计算区间是i - j (包括j)，为了解决索引从0开始的问题，所以结果列表的第一位补0，j要向后延一位。那么我们求结果就用retLst[j+1]索引的值减去retLst[i]位的值就可以了
- tips:看题解思路没有那么多的条件过滤，为了代码简洁，索性就去掉了。
class NumArray:
def __init__(self, nums: List[int]):
self.retLst = [0] * (len(nums) + 1)
for i in range(len(nums)):
self.retLst[i+1] = self.retLst[i] + nums[i]
def sumRange(self, i: int, j: int) -> int:
return self.retLst[j+1] - self.retLst[i]
