题目描述
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:
You may assume that the array does not change.There are many calls to sumRange function.给定一个数组，调用sumRange函数求某个子区间的和。
解题思路
大体思想 sumRange（i，j） ＝ sumRange（0，j）－ sumRange（0， i－1）
解法一（超时）
构造一个sum数组，存放（0，x）的和，x是全部的下标，在构造函数中计算整个sum
代码：
class NumArray { public: vector<int> sum; NumArray(vector<int> nums) { sum.resize(nums.size(), 0); for (int i = 0; i < nums.size(); i++) { for (int j = 0; j <= i; j++) sum[i] += nums[j]; } } int sumRange(int i, int j) { if (i == 0) return sum[j]; return sum[j] - sum[i - 1]; } }; /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(i,j); */
当数组十分巨大时，构造函数O（n^2）会很慢。
解法二：
并不先 全部计算出sum数组，有需要时才计算，也就是，当需要sum（0，x）且sum（0，x）＝＝0时计算出sum（0，x）。因此还需要额外的数组tmp记录nums。而且随着调用sumRange次数越来越多，整个sum数组几乎被填满，此时会很快。
代码
class NumArray { public: vector<int> sum; vector<int> tmp; NumArray(vector<int> nums) { sum.resize(nums.size(), 0); tmp = nums; } int sumRange(int i, int j) { if (i == 0) { if (sum[j] == 0) { for (int p = 0; p <= j; p++) sum[j] += tmp[p]; } return sum[j]; } else { if (sum[i - 1] == 0) { for (int p = 0; p <= i - 1; p++) sum[i-1] += tmp[p]; } if (sum[j] == 0) { for (int p = 0; p <= j; p++) sum[j] += tmp[p]; } return sum[j] - sum[i - 1]; } } }; /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(i,j); */
（虽然ac了，可是时间是1192ms，大神们的时间是200ms左右，丢人了，丢人了，但是这道easy的通过率是28%，挺奇怪）
