給定一個(gè)整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和，包含 i、j 兩點(diǎn)。
實(shí)現(xiàn) NumArray 類：
NumArray(int[] nums) 使用數(shù)組 nums 初始化對(duì)象
int sumRange(int i, int j) 返回?cái)?shù)組 nums 從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和，包含 i、j 兩點(diǎn)（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
提示：
0 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= i <= j < nums.length
最多調(diào)用 104 次 sumRange 方法

示例：

輸入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
輸出：
[null, 1, -1, -3]

解釋：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

解題步驟

1、存儲(chǔ)數(shù)組 nums 的值，每次調(diào)用sumRange 時(shí)，通過循環(huán)的方法計(jì)算數(shù)組nums從下標(biāo) i 到下標(biāo) j 范圍內(nèi)的元素和，需要計(jì)算 j-i+1 個(gè)元素的和,由于每次檢索的時(shí)間和檢索的下標(biāo)范圍有關(guān)，因此檢索的時(shí)間復(fù)雜度較高，如果檢索次數(shù)較多，則會(huì)超出時(shí)間限制,所以先用一個(gè)數(shù)組，計(jì)算并存儲(chǔ)每個(gè)下標(biāo)處的前綴和，這樣減少時(shí)間復(fù)雜度
2、將前綴和數(shù)組sums的長度設(shè)為 n+1 的目的是為了方便計(jì)算 sumRange(i,j)，不需要對(duì) i=0 的情況特殊處理，這樣計(jì)算一個(gè)范圍得值就變成了 j+1-i

代碼

class NumArray {
    int[] sums;

    public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}