【题目描述】
给定一个整数数组 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 方法。
【思路1】
1、直接累加，每调用一次sumRange方法 累加一次
2、时间复杂度O(n) 每次调用都为O(n)
3、空间复杂度O(1)
Swift代码实现：
class NumArray {
var arr : [Int]?
init(_ nums: [Int]) {
arr = nums
}
func sumRange(_ i: Int, _ j: Int) -> Int {
var sum = 0
if i <= j && i<arr!.count && j<arr!.count {
for k in i...j {
sum+=arr![k]
}
}
return sum
}
}
【思路2】
1、把每次相加的结果缓存
2、(i,j)的结果为 arr[j]-arr[i]
3、时间复杂度为O(n)，其后每次调用为O(1)
4、空间复杂度O(n)
5、【官方】在下面的代码中，我们插入了一个虚拟 0 作为 sum 数组中的第一个元素。这个技巧可以避免在 sumrange 函数中进行额外的条件检查，妙哉！
Swift代码实现：
class NumArray {
var sum = [Int]()
init(_ nums: [Int]) {
sum = Array.init(repeating: 0, count: nums.count+1)
for k in 0..<nums.count {
sum[k+1] = sum[k]+nums[k]
}
}
func sumRange(_ i: Int, _ j: Int) -> Int {
return sum[j+1] - sum[i]
}
}
