Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

1
2
3
4
5
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.

  2. There are many calls to sumRange function.

思路

一开始觉得用用暴力算法没啥问题，但是发现超时了。原因是在测试的时候，会多次调用sumRange函数，如果调用n次，数组长度为m，最坏的情况当然是达到了O(n*m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumArray(object):
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.n = nums
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        res = 0
        for k in range(i,j+1):
            res += self.n[k]
        return res
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

所以我们考虑利用动态规划来降低复杂度。实际上也是一种典型的空间换时间的方法。

另外声明一个数组n。遍历原数组，将当前元素前，所有元素的和，放进数组n对应的位置当中。

这样在每次调用sumRange的时候，复杂度都是O(1)，超时的问题也就解决了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class NumArray(object):
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.n = []
        res = 0
        for i in nums:
            res += i
            self.n.append(res)
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        left = 0
        right = 0
        if (i != 0):
            left = self.n[i-1]
        right = self.n[j]
        return right - left
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)