博客

基本思路：

暴力搜索比较简单，直接算区间，但是衍生出一个所谓的前缀和的思路；

前缀和有点像DP+打表；

具体思路是建立数组n，n长度为length+1，并且n[i]表示前n-1位的和；

如此，如果求i～j元素的和，只需要用前j位元素的和减去前i-1位元素的和，即为标准答案；

即：n[j+1]-n[i]，注意一下n的实际含义，就很容易理解，不然还需要额外开数组；

基本代码：

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

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