Leetcode No.303区域和检索-数组不可变

题目大意

给定一个整数数组 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
说明：
1.你可以假设数组不可变。
2.会多次调用 sumRange 方法。

方法一：暴力法

直接遍历i到j的数组，计算sum。

private int[] data;
    public NumArray(int[] nums) {
         data = nums;
    }
public int sumRange(int i, int j) {
        int sum = 0;
        for (;i<=j;i++)
            sum+=data[i];
        return sum;
    }

运行时间551ms,击败7.06%。

方法二：动态规划

sum[k]表示下标0...k-1的序列和。

private int[] data;
private int[] sum;
public NumArray(int[] nums) {
        data = nums;
        sum = new int[nums.length+1];
        for(int i=0;i<nums.length;i++)
            sum[i+1]=sum[i]+nums[i];
    }
public int sumRange(int i,int j) {
        return sum[j+1]-sum[i];
    }

注意：这里有个技巧是设置一个虚拟0，避免一些越界操作。