LeetCode Range Sum Query – Immutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example:

Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

---

给定一个固定的数组，要查询某个区间[i,j]之间的和，且这样的查询很多。 明显需要先把结果存起来，这样每次查询的时候直接返回就好。用数组dp[i]表示区间[0,i]之间的和，这样区间[i,j]的和=dp[j]-dp[i-1]。注意当i=0的情况。完整代码如下： [cpp] class NumArray { private: vector<int> dp; public: NumArray(vector<int> nums) { int n = nums.size(); if (n == 0)return; dp.resize(n); dp[0] = nums[0]; for (int i = 1; i < n; ++i)dp[i] = dp[i – 1] + nums[i]; } int sumRange(int i, int j) { if (dp.empty())return 0; return dp[j] – (i == 0 ? 0 : dp[i – 1]); } }; [/cpp] 本代码提交AC，用时206MS。]]>