【題目描述】
給定一個整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j (i ≤ j) 范圍內元素的總和啸箫，包含 i, j 兩點。
【示例】
給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數(shù)為 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
【說明】
1羹应、你可以假設數(shù)組不可變。
2次屠、會多次調用 sumRange 方法园匹。
【思路1】
1雳刺、直接累加，每調用一次sumRange方法 累加一次
2裸违、時間復雜度O(n) 每次調用都為O(n)
3掖桦、空間復雜度O(1)
Swift代碼實現(xiàn)：
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 數(shù)組中的第一個元素趁舀。這個技巧可以避免在 sumrange 函數(shù)中進行額外的條件檢查赖捌，妙哉！
Swift代碼實現(xiàn)：
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]
}
}
