LeetCode 303 区域和检索 - 数组不可变

LeetCode 动态规划相关

问题

给定一个整数数组 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 方法。

解答

我们可以新建一个数组，用来存放index 0 到后面index 1 2 3 4 5...的元素和

如上述示例，nums = [-2, 0, 3, -5, 2, -1]，那么新建的数组res，里面的数据为

res[0, 0] = nums[0] = -2
res[0, 1] = nums[0] + nums[1] = res[0, 0] + nums[1] = -2
res[0, 2] = nums[0] + nums[1] + nums[2] = res[0, 1] + nums[2] = 1
...
res[0, 5] = res[0, 4] + nums[5]

由于题目要求计算的是i到j的元素和，那么就可以这样：

sumRange(1, 1) = res[0, 1] - res[0, 0] = 0
sumRange(1, 2) = res[0, 2] - res[0, 0] = 3
sumRange(1, 3) = res[0, 3] - res[0, 0] = -2
...
sumRange(2, 4) = res[0, 4] - res[0, 1] = 0
...

所以代码如下：

class NumArray {
    int[] res;
    public NumArray(int[] nums) {
        int n = nums.length;
        res = new int[n];
        if(n > 0) {
            res[0] = nums[0];
            for(int i = 1; i < n; i++) {
                res[i] = res[i - 1] + nums[i];
            }
        }
    }

    public int sumRange(int i, int j) {
        if(i == 0)
            return res[j];
        else
            return res[j] - res[i - 1];
    }
}

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