区域和检索——数组不可变

前两天终于实现了翻墙，现在开刷leetcode,久闻大名，今天才开始真是惭愧！

刷题的奥义在于一定要分tag,一段时间（比如一周）只刷一种能行，浅尝辄止随便去刷很容易忘记，单恋一种题型又容易被困住思维，本周我选择动态规划！刷个十道,同时C++和java混用着做

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:

你可以假设数组不可变。
会多次调用 sumRange 方法。

其实这道题不难，一眼就看出用数组循环

class NumArray {
public:
    vector<int> nums;
    NumArray(vector<int> nums) {
        this->nums=nums;
    }
    
    int sumRange(int i, int j) {
        int sum=0;
        for(int b=i;b<j+1;b++){
            sum+=nums[b];
        }
        return sum;
    }
};

然而显示我速度只超过了2%的人，为什么不贴java的，因为java直接超时，过不了！

上面的代码的问题在于，当测试用例过多时，每次都必须重新计算，但实际上，由于数组没变，所以可以事先计算好大部分数据，用另外一个数组来保存，而此时，就用动态规划来保存

class NumArray {
    int [] nums;
    int len;
    int [] sum;
    public NumArray(int[] nums) {
        this.nums=nums;
        len=nums.length;
        if(len>0){
            sum=new int [len+1]
            for(int i=1;i<len+1;i++)
            //sum[i]不包括nums[i],因为sumRange中会被减掉
            sum[i]=sum[i-1]+nums[i-1];
        }
    }
    public int sumRange(int i, int j) {
        int s=0;
        s=sum[j+1]-sum[i];
        return s;
    }
}

上面的代码不仅可以用java，而且超过了80%的人哦！

那你可能会好奇，最快的代码是什么样的呢？
下面这个，同样的动态规划，用时只有我的一半！

class NumArray {

    int[] nums;
    public NumArray(int[] nums) {
    //这里全盘使用this指针，创建的变量数达到最少
        this.nums = new int[nums.length];
        if(this.nums.length == 0) return;
        this.nums[0] = nums[0];
        for(int i=1; i<nums.length;i++) {
            this.nums[i] = this.nums[i-1] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
    //这里他没有新设变量，而是直接返回结果
        return i==0? nums[j]:nums[j]-nums[i-1];
    }
}