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

题目

题目链接🔗
给定一个整数数组 $nums$，处理以下类型的多个查询:

计算索引 $left$ 和 $right$ （包含 $left$ 和 $right$）之间的 $nums$ 元素的 和 ，其中 $left\le right$
实现 $NumArray$ 类：

$NumArray(int[]nums)$ 使用数组 $nums$ 初始化对象
$int$ $sumRange(inti,intj)$ 返回数组 $nums$ 中索引 $left$ 和 $right$ 之间的元素的 总和 ，包含 $left$ 和 $right$ 两点（也就是 $nums[left]+nums[left+1]+...+nums[right]$ )

示例 1：
输入：
[“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))
提示：

• $1\le nums.length\le 10^4$
• $-10^5\le nums[i]\le 10^5$
• $0\le i\le j<nums.length$
• 最多调用 $10^4$ 次 $sumRange$ 方法

思路

这道题很明显就是一道前缀和模板题目，使用一个数组记录前面$i$个元素的和，然后后面就可以使用$O(1)$的时间复杂度计算给定区间的和。

代码

class NumArray {
public:
    vector<int> sum;
    NumArray(vector<int>& nums) {
        int n = nums.size();
        sum.resize(n + 1);
        sum[0] = 0;
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }
    }
    int sumRange(int left, int right) {
        return sum[right + 1] - sum[left];
    }
};

复杂度分析

时间复杂度

计算前缀和：$O(n)$
单次计算区间和：$O(1)$

空间复杂度

$O(n)$

结果

总结

这道题目是一道经典的前缀和问题，采用了构建前缀和数组的方法，使得在 $O(1)$ 时间内能够计算任意给定区间的元素和。通过预处理阶段计算前缀和，并在查询阶段利用前缀和数组的性质，避免了重复计算区间和，从而提高了查询效率。