LeetCode Range Sum Query - Immutable

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:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.   

这个问题的关键是不能按照传统的求值方法。。如果每次求结果按照以前我们经常用的按顺序相加，在LeetCode是不能通过的，会超时，我们应该将其全部求和，前N次求和放到容器中

class NumArray {
public:
    NumArray(vector<int> &nums) {
        int sum = 0;
        for (int i = 0;i<nums.size();++i)
        {
            sum += nums[i];
            number.push_back(sum);
        }

    }

    int sumRange(int i, int j) {
        if (i == 0)return number[j];
        else return number[j] - number[i - 1];
    }
private:
    vector<int> number;
};

LeetCode Range Sum Query - Immutable

原文：http://www.cnblogs.com/csudanli/p/4967716.html