LeetCode 303 Range Sum Query

翻譯

給定一個整型數組nums，找出在索引i到j（i小於等於j）之間（包括i和j）的所有元素之和。

例如：
給定nums = [-2,0,3,-5,2,-1]

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

批注：
你可以假定這個數組不會改變。
這裡會有很多次對sumRange函數的調用。

原文

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
Note:
You may assume that the array does not change.
There are many calls to sumRange function.

分析

一開始我還以為這個題有多簡單呢，就寫了下面這個代碼：

class NumArray {
public:
    vector numArray;
    NumArray(vector &nums) {
        numArray = nums;
    }
    int sumRange(int i, int j) {
        int sum = 0;
        while (i < j) {
            sum += numArray[i++];
        }
        return sum;
    }
};

因為不知道需要構造函數干嘛，所以硬生生的加了這麼一句進去，其實完全沒用。功能是實現了，但是面對題目變態的測試用例，果然還是崩了。

至於題目測試用例有多變態，數據來說話：一共214513個字符，其中包括了nums的數據，也包括了函數調用，nums的長度沒去算，但是sumRange函數的調用次數高達10000次。

看到這個測試用例，就明白要針對函數調用做優化，一個不錯的辦法是將所有的返回的值：

從0到1的所有元素之和，
從0到2的所有元素之和，
從0到10000的所有元素之和，
………………

然後計算i和j之間所有元素之和的時候，（因為包含了i和j），也就是求從0到j的所有元素之和減去從0到i-1的所有元素之和。

所以代碼就如下所示了，但是時間上還是使用了624ms叻。

class NumArray {
public:
    map rangeSum;
    NumArray(vector &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            rangeSum.insert(pair(i, sum));
        }
    }

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

雖然對底層的具體實現不是很了解，但因為有索引，所以我自覺用vector的話查找其值來跟快速；而且添加值也更加快速，因為只是一個值而不用是鍵值對。

具體代碼如下：

代碼

class NumArray {
public:
    vector rangeSum;

    NumArray(vector &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            rangeSum.push_back(sum);
        }
    }

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