[leetcode] 303 区域和

给定一个整数数组  nums,求出数组从索引 i 到 ji ≤ j)范围内元素的总和,包含 i两点。

实现 NumArray 类:

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 从索引 i 到 ji ≤ j)范围内元素的总和,包含 i两点(也就是 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]
上一篇:如何将less编译成css文件__less自动编译成css的方法总结


下一篇:织梦dedecms百度快照劫持注入代码防范与清除