leetCode-303:Range Sum Query - Immutable

问题描述

给定一个整形数组，要求多次查询数组中某个区间的元素之和。题目链接：**点我**

样例输入输出

输入：

[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

输出：[null, 1, -1, -3]

解释：

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

问题解法

最直接的方式就是按照输入的下标，使用循环进行累加，这对一次查询是有效的，不过在多次查询的情况下，如果每次都使用循环进行累加，时间复杂度比较高。优化点的做法是使用数组保存当前元素之前所有元素的和（包括当前元素），然后在输入下标计算区间和的时候使用 dp[right] - dp[left - 1] 即可获得答案。这样多次查询的情况下也只有一次循环，时间复杂度为 O(n)。代码如下

class NumArray {
    int[] prefixSum;

    public NumArray(int[] nums) {
        prefixSum = new int[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (left == 0) {
            return prefixSum[right];
        }

        return prefixSum[right] - prefixSum[left - 1];
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */