LeetCode 303 Range Sum Query - Immutable（范围总和查询-永久不变）（*）

翻译

给定一个整型数组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<int> numArray;
    NumArray(vector<int> &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<int, int> rangeSum;
    NumArray(vector<int> &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            rangeSum.insert(pair<int, int>(i, sum));
        }
    }

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

虽然对底层的具体实现不是很了解，但因为有索引，所以我自觉用vector的话查找其值来跟快速；而且添加值也更加快速，因为只是一个值而不用是键值对。

具体代码如下：

代码

class NumArray {
public:
    vector<int> rangeSum;

    NumArray(vector<int> &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];
    }
};