问题：

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) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3

Note:

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

题目大意：

自己构造一个类，构造函数传入一数组，求和函数给一个起始下标，一个终止下标，求这个闭区间的和。

初始思路：

类中有一个数组，构造函数把传入的数组赋值给类的数组。

求和时从起始下标开始遍历至终止下标。

class NumArray {public:    NumArray(vector
     
       &nums) {        arr = nums;    }    int sumRange(int i, int j) {        int sum = 0;        while (i <= j)        {            sum += arr[i];            i++;        }        return sum;    }private:    vector
      
        arr;};
      
     

这种思路中，复杂度为O(j-i)（O(n)），题目中说sum函数会频繁调用，复杂度不好，结果是超时。

改进思路：

因为频繁的使用sum函数，需要降低该函数的复杂度。降低的方法从构造函数入手，使得类内的数组存着sum值，这样可以得到复杂度O(1)的sum函数。

class NumArray {public:    NumArray(vector
     
       &nums) {        arr.push_back(0);        for (int i = 1; i<=nums.size(); i++)            arr.push_back(arr[i - 1] + nums[i-1]);    }    int sumRange(int i, int j) {        return (arr[j + 1] - arr[i]);    }    vector
      
        arr;};
      
     

这段代码的关键在构造函数，这里类中的arr数组下标i存的是nums数组前i-1个元素的和。每次将前一个sum元素加num元素得到一个sum元素追加到尾部，相当于遍历了一遍num数组，构造函数的复杂度是O(n)。值得注意的是，采用一般的思路时，构造函数的复杂度也是O(n)。

总结

这道题看起来非常简单，即使初学者也可完成，但想要降低复杂度就需要一个巧妙的算法。

题目中自己编写的代码不知是一个求和函数，而是一个类(包括构造函数），这应该是一个很强的提示，要利用只调用一次的构造函数，去降低sum函数的复杂度。

题目另一个提示就是There are many calls to sumRange function.这也体现了需要降低sum函数复杂度的需求。

这是本人第一道leetcode题目，以后要加油啊~