LeetCode 303. 区域和检索 - 数组不可变 Rang

【题目描述】
给定一个整数数组 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]
    }
}