LeetCode 303. Range Sum Query - Immutable

题目

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

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

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

Note:

  • You may assume that the array does not change.
  • There are many calls to sumRange function.

分析

实现列表的区间和函数

  • 条件:假设输入的数组不变,且会经常调用,要求性能高,常数时间返回

代码

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
'''
The idea is fairly straightforward: create an array accu that stores the accumulated sum for nums such that accu[i] = nums[0] + ... + nums[i - 1] in the initializer of NumArray. Then just return accu[j + 1] - accu[i] in sumRange. You may try the example in the problem statement to convince yourself of this idea.
'''
class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
self.accu = [0]
for num in nums:
self.accu += self.accu[-1] + num,
def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
return self.accu[j + 1] - self.accu[i]
# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.sumRange(1, 2)

点评

初始化的时候,保存一个数组的累积和