题目描述
给定一个整数数组 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 方法。
不直接存储结果,存储从第一个元素到第i个元素的和dp[i] = sum(nums[0]~nums[i-1]);
动态转移方程:
dp[i] = dp[i-1] + nums[i-1];
res = dp[j+1] - dp[i];
初始条件
dp[0] = 0
dp尺寸为N+1
因为你要保证i=j的时候不会return 0 , 而应该return nums[j],所以dp的尺寸应该为N+1,result[i][j] = dp[j+1] - dp[i]。换句话说当i=0, j=0时,result[0][0] = dp[1] - dp[0] = nums[0];
C++ 代码
class NumArray {
public:
NumArray(vector<int>& nums) {
if(!nums.empty())
{
vector<int> dp(nums.size() + 1, 0);
for(int i = 0; i < nums.size(); ++i)
dp[i + 1] = dp[i] + nums[i];
res = dp;
}
}
int sumRange(int i, int j) {
return res[j + 1] - res[i];
}
private:
vector<int> res;
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(i,j);
*/