博客

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

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:

1. 你可以假设数组不可变。
2. 会多次调用 sumRange 方法。

第一种思路：

二维打表法。

简单粗暴，但是会卡在最后一个test case上，内存不够用。

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        m = len(nums)
        n = m
        self.dp =[[[0] for _ in range(m)] for i in range(n)]
        
        for i in range(0, m):
            self.dp[i][i] = nums[i]
        
        for i in range(m):
            for j in range(i + 1,n):
                self.dp[i][j] = self.dp[i][j - 1] + nums[j]

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.dp[i][j]
        


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

第二种思路：

优化一下，其实一维打表就够了，用 dp[i] 储存 0 – i 的元素之和，如果求 i – j 的元素之和，就返回dp[j] – dp[i – 1]即可。

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        if not nums:
            return None
        m = len(nums)
        n = m
        self.dp = [0 for _ in range(m)]
        
        self.dp[0] = nums[0]
        
        for i in range(1, m):
            self.dp[i] = self.dp[i - 1] + nums[i]
        
        # print self.dp
        
    
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if i == 0:
            return self.dp[j]
        else:
            return self.dp[j] - self.dp[i - 1]
        


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)