前两天终于实现了***,现在开刷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];
    }
}