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：

输入：
[“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))

说明

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

思路

• 无脑暴力解：
  1. 把nums中的i~j相加并返回
  2. 当我们调用sumRange()时，均需要循环n次
• 前缀和：
  1. 相加的环节我们放到构造函数中，这样的话我们在构造时只执行一遍
  2. 当我们调用 sumRange()时，只要执行1次便可

代码实现

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
26
27
28
29
30
31
32
33
34

//无脑暴力解
class NumArray {
public:
    vector<int> numbers;

    NumArray(vector<int>& nums) {
        numbers = nums;
    }
    
    int sumRange(int i, int j) {
        int res = 0;
        for(int a = i;a<=j;a++){
            res+=numbers[a];
        }
        return res;
    }
};

//前缀和
class NumArray {
public:
    vector<int> numbers;

    NumArray(vector<int>& nums) {
        numbers.resize(nums.size()+1);
        for(int i = 0;i<nums.size();i++){
            numbers[i+1] = numbers[i] + nums[i];
        }
    }
    
    int sumRange(int i, int j) {
        return numbers[j+1] - numbers[i];
    }
};