【3.1】LeetCode每日一题· 区域和检索 - 数组不可变

2021年03月01日 10时25分

标签： LeetCode 数组前缀和

## 题目描述
给定一个整数数组`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])`）

#### 示例
	输入：
	["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 方法

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/range-sum-query-immutable/ "题目链接")

## 解题思路
`nums`的长度$$N$$为$$10^4$$量级，而sumRange的调用次数也达到$$10^4$$，如果直接采取暴力解法，每一次求和就遍历区间中的所有元素求和的话，一定会超时。
因此可以采用前缀和。由于

$$\displaystyle \sum\_{k=i}^j nums[k] = \sum\_{k=0}^j nums[k] - \sum\_{k=0}^{i-1} nums[k], $$

因此我们可以首先在$$O(n)$$时间内预处理出数组的前缀和，然后需要查询区间和时，使用$$O(1)$$的时间计算两个前缀和之差即可。
时间复杂度$$O(n)$$，空间复杂度$$O(n)$$。

##代码
	class NumArray {
	public:
		vector<int> diff;
		NumArray(vector<int>& nums) {
			if(nums.size()==0) return;
			diff.push_back(nums[0]);
			for(int i = 1; i < nums.size(); i++){
				diff.push_back(nums[i] + diff[i-1]);
			}
		}

int sumRange(int i, int j) {
			if(i==0) return diff[j];
			return diff[j] - diff[i-1];
		}
	};

/**
	 * Your NumArray object will be instantiated and called as such:
	 * NumArray* obj = new NumArray(nums);
	 * int param_1 = obj->sumRange(i,j);
	 */

## 用时和内存
> 执行用时：12 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：16.8 MB，在所有 C++提交中击败了57.09%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.1】LeetCode每日一题· 区域和检索 - 数组不可变

所有评论

暂无评论

新增评论