本题的意思是给定一个整数数组nums，求若干次下标i到下标j之间的元素之和。
最简单的想法是每次求和的时候，都把下标i到下标j之间的元素一个个加起来，但是这样做的时间复杂度太高，每次求和都要O(n)的时间。
这里，我采用动态规划的算法来解决此题。我先算出从nums[0]到数组每个元素之间的n个和，只需要O(n)的时间复杂度，然后将这n个和存储起来。这样，任意下标i到下标j之间的元素之和我们都可以直接由存储的n个和中算出，时间复杂度为O(1)。
class NumArray { public: NumArray(vector<int> nums) { if (!nums.empty()) { sum.push_back(nums[0]); for (int i = 1; i < nums.size(); ++i) { sum.push_back(sum[i - 1] + nums[i]); } } } int sumRange(int i, int j) { if (sum.empty()) { return 0; } if (i == 0) { return sum[j]; } else { return sum[j] - sum[i - 1]; } } private: vector<int> sum; }; /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(i,j); */