筆記：【演算法新手村】[初階]筆記04 - 前綴和(一維)

題目翻譯

給定一個整數陣列 nums，請處理多個以下類型的查詢：
計算 nums 在索引 left 到 right 之間（包含 left 與 right）所有元素的總和。
實作 NumArray 類別：
NumArray(int[] nums)：使用整數陣列 nums 初始化物件。
int sumRange(int left, int right)：回傳陣列中從索引 left 到 right 之間元素的總和（即 nums[left] + nums[left + 1] + ... + nums[right]）。

限制：
1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= left <= right < nums.length
最多呼叫 10⁴ 次sumRange.

解題思路

看到大量呼叫跟求和函式，這題要使用前綴和優化應該不難看出，大致內容也都差不多。唯一需要注意的是，由於題目給我們的陣列是從0開始(0-based)，會跟之前有一些的不同，不過具體概念都是一樣的，我這邊的定義是：prefix[i] 是 nums[0] 一直累加到 nums[i]，求區間公式上要特別注意索引越界問題(left如果是0，left-1 = -1，屬於非法索引)，除此之外沒什麼要注意的了，簡單下班~

程式碼實作 (C++)

class NumArray {
public:
    vector<int> prefix;
    NumArray(vector<int>& nums) {
        int n = nums.size();
        prefix.reserve(n);
        prefix[0] = nums[0];
        for(int i = 1 ; i < n ; i++){
            prefix[i] = prefix[i-1] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        if(left == 0) return prefix[right];
        return prefix[right] - prefix[left-1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */