https://leetcode.com/problems/range-sum-query-immutable/#/description

Paste_Image.png

方法1: 直接求和

• 又是有一个超长Array会导致超时

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
        """
        s = 0
        for k in range(i, j+1):
            s += self.nums[k]
        return s

方法2: 空间换时间

• 初始化nums的累加数组cusum
• 例如[1, 2, 3]的累加数组为[0, 1, 3, 6]
• sumrange(0, 1) = cusum(1+1) - cusum(0)
• sumrange直接读取cusum中的元素相减即可
• Space O(n)
• Time O(1)

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.cusum = [0]
        for num in nums:
            self.cusum += [self.cusum[-1] + num]
        

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.cusum[j + 1] - self.cusum[i]