leetcode筆記：Range Sum Query

一. 題目描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

二. 題目分析

給定一個數組nums，求出下標i和j之間元素的和，這裡假設i一定是小於或等於j的，且數組nums一般是不變的。

這道題應該不看提示就能想到比暴力方法更好的方案，在本題中，sumRange可能會被調用多次，因此如果每次調用時才對下標區間的元素進行累加，會導致效率低下。

可以采取的改進方法是，在構造函數NumArray(vector &nums)中，輸入了數組nums，同時計算了從第一個元素到每個下標元素所有元素的累積和，保存到新數組sums的對應位置中，這樣，每次尋找下標i和j之間元素的和，只需直接返回： sums[j] - sum[i - 1]即可。

三. 示例代碼

class NumArray {
public:
    NumArray(vector &nums) {
        if (nums.empty()) return;
        else
        {
            sums.push_back(nums[0]);
            //求得給定數列長度
            int len = nums.size();
            for (int i = 1; i < len; ++i)
                sums.push_back(sums[i - 1] + nums[i]);
        }
    }

    int sumRange(int i, int j) {
        return sums[j] - sums[i - 1];
    }

private:
    //存儲數列和
    vector sums;
};

// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);