[DP]303——Range Sum Query - Immut

Range Sum Query - Immutable

思路:
动态规划，每次计算和的时候用上一次计算的结果。时间复杂度为O(n)。不用的话时间复杂度为O(n2). Table 方便查询

比如nums长度是n 查询m次 就是O(nm)
但是存一个NumArray[i]，表示从0－i的sum和，那么查询sum[i,j]即为sum[0,j] - sum[0,i]

Runtime Error

class NumArray {
    int sum[];
    public NumArray(int[] nums) {
        int len = nums.length;
        sum = new int[len];
        sum[0] = nums[0];
        for (int i = 1; i< len; i++){
            sum[i] = sum[i-1] + nums[i];
        }
        
    }
    
    public int sumRange(int i, int j) {
        if(i < 0 || j >= sum.length || i >j )return 0;
        if(i == 0) return sum[j];
        else return sum[j]-sum[i-1];
        
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

看来查询nums也很占时间啊。。小小改动就accept了

class NumArray {
    int sum[];
    public NumArray(int[] nums) {
        int len = nums.length;
        sum = nums.clone();
        for (int i = 1; i< len; i++){
            sum[i] += sum[i-1];
        }
        
    }
    
    public int sumRange(int i, int j) {
        if(i < 0 || j >= sum.length || i >j )return 0;
        if(i == 0) return sum[j];
        else return sum[j]-sum[i-1];
        
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */