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下标间所有数字的和。结合题目中给出的提示代码来看：
class NumArray { public: NumArray(vector<int> nums) { } int sumRange(int i, int j) { } }; /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(i,j); */题目的意思是首先需要根据给出的数组nums创建一个对象Numarray，然后使用这个对象中的函数sumRange完成前面的要求。而sumRange是会进行多次调用的，在不断调用sumRange中间数组不变。如果仅仅是将原本的数组存到对象中是没有什么意义的。如果使用mynums[k]表示数组中前k个数的总和，这样在计算i，j下标间所有数字的和的时候只需计算mynums[j + 1] - mynums[i]即可。 具体实现代码如下所示，在创建mynums数组时的时间复杂度为 O(n) ，sumRange函数的时间复杂度为 O(1) ，空间复杂度为 O(n) 。
class NumArray { public: NumArray(vector<int> nums) { mynums.push_back(0); for(int num : nums){ mynums.push_back(num + mynums.back()); } } int sumRange(int i, int j) { return mynums[j + 1] - mynums[i]; } private: vector<int> mynums; };