区间和查询-前缀和数组

在这里插入图片描述

解题思路

这道题直接暴力求和每次都要遍历区间内所有元素，时间复杂度 O(n)，而前缀和可以将查询优化到 O(1)。

预先计算一个长度为 n+1 的数组 sum（若原数组长度为 n），之所以多一个位置，是为了把 sum[0] 作为“前 0 个元素的和 = 0”占位，这样后续 sum[i] 可以统一表示原数组前 i 个元素之和（注意：sum[i]对应 nums[0]..nums[i-1]）。

构造时从左到右遍历，利用递推关系 sum[i] = sum[i-1] + nums[i-1] 完成预处理。

查询区间 [left, right] 的和时，把区间求和转化为两个前缀和的差值运算，只需要用 sum[right+1] - sum[left] 即可。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class NumArray {
    public int[] sum;

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

    public int sumRange(int left, int right) {
        return sum[right + 1] - sum[left];
    }
}

如果觉得有帮助，欢迎点赞、关注、转发~