[leetcode]303-区域和检索（数组不可变）

马谦马谦马谦

615
文章

17
评论

2020年2月9日17:10:14数据结构和算法评论189字数 959阅读3分11秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/range-sum-query-immutable

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()。

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

sumRange(0, 2) -> 1

sumRange(2, 5) -> -1

sumRange(0, 5) -> -3

说明：

你可以假设数组不可变。
会多次调用 sumRange 方法。

二、题解

题目很迷幻，一眼看上去可能会误解成就是求指定区间的和，如果只是求指定区间内的和，除了遍历就没有其他办法了。而实际上整道题目的重点就是会多次调用，也就是说同一份数据，会有多个测试案例。

很容易能猜出最容易出现问题的地方就是超时了，因为实际的问题很简单，就是求和，求和只能遍历，不可能就这么简单每次就遍历求和。因此考虑的重点就在于如何在多次调用中减少时间占用。

减少计算时间的办法：缓存数据，即缓存下来部分数据的和，再根据缓存的和来计算特定范围的和。

以测试数据为例，以sum[i]表示下标i以前（不包括i）的所有数据之和，那么sum数组的值为：

0, -2, -2, 1, -4, -2, -3

1	0, -2, -2, 1, -4, -2, -3

sumRange(0, 2)就相当于计算sum[2 + 1] - sum[0] ，值为1。

sumRange(2, 5)就相当于计算sum[5 + 1] - sum[2]，值为-2。

在这种情况下能总结出来的规律是：sumRange(i, j) = sum[j + 1] - sum[i]。

三、代码

逻辑很简单，但关键点是：sum[i]表示的是i以前所有元素的和，所以要给sum[0]赋值上一个0值。

class NumArray {
private:
    vector<int> sum;
public:
    NumArray(vector<int>& nums) {
        // 构造函数中初始化sum数组
        size_t i;
        // 给sum[0]附上一个0值
        sum.push_back(0);
        for (i = 0; i< nums.size(); i++) {
            sum.push_back(sum[i] + nums[i]);
        }
    }

    int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
};

class NumArray {

private:

vector<int> sum;

public:

NumArray(vector<int>& nums) {

// 构造函数中初始化sum数组

size_t i;

// 给sum[0]附上一个0值

sum.push_back(0);

for (i = 0; i< nums.size(); i++) {

sum.push_back(sum[i] + nums[i]);

}

int sumRange(int i, int j) {

return sum[j + 1] - sum[i];

}

};

[leetcode]303-区域和检索（数组不可变）

优化

可以看到，时间消耗还是很大的，排名才击败了38%。代码中主要的耗时是vector数组的扩容导致的，因为够早的时候需要频繁push_back导致数组扩容和内存拷贝，比较费时。可以把vector改成数组形式，手动分配内存空间，减少vector频繁扩容。

class NumArray {
private:
    int *sum;
public:
    NumArray(vector<int>& nums) {
        size_t i;
        sum = new int[nums.size() + 1];
        sum[0] = 0;
        for (i = 0; i< nums.size(); i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
};