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

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例：

1
2
3
4
5
6
7
8
9
10
11
输入：
["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 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

前缀和概念的首次应用，在求连续元素的和的情况下尤其好用

Solution

题目要求是返回一个数组间从下标i到下标j元素之间的和，如果采用暴力算法，循环计算，由于每次检索的时间和检索的下标范围有关，因此时间复杂度较高

所以能实现计算出前缀和，那么可以将时间复杂度降低到O(1)

具体实现方面，假设数组 nums 的长度为 n，创建长度为 n+1 的前缀和数组sums，对于0≤i＜n都有sums[i+1]=sums[i]+nums[i]，sums[i]表示数组nums从下标0到下标i-1的前缀和

前缀和计算方法：sumRrage(i,j)=sums[j+1]-nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class NumArray {
    // sums数组用于存储累积和，其中sums[i]表示从数组开始到元素nums[i-1]的累积和
    int[] sums;

    // 构造函数接收一个整数数组nums作为参数
    public NumArray(int[] nums) {
        int n = nums.length;
        // 初始化sums数组，长度为n+1，多出的一个位置用于方便地计算累积和（sums[0]默认为0）
        sums = new int[n + 1];
        // 遍历nums数组，计算每个位置的累积和并存储在sums数组中
        for (int i = 0; i < n; i++) {
            // sums[i+1]存储从nums[0]到nums[i]的累积和
            sums[i + 1] = sums[i] + nums[i];
        }
    }
    
    // sumRange方法接收两个参数i和j，返回数组中从索引i到索引j的元素和
    public int sumRange(int i, int j) {
        // 通过sums数组快速计算区间和，即sums[j+1] - sums[i]
        // sums[j+1]表示从nums[0]到nums[j]的累积和，sums[i]表示从nums[0]到nums[i-1]的累积和
        // 因此，二者之差正好是从nums[i]到nums[j]的元素和
        return sums[j + 1] - sums[i];
    }
}