给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:

1. 你可以假设数组不可变。
2. 会多次调用 sumRange 方法。

 

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

static int x = []() {std::ios::sync_with_stdio(false); cin.tie(0); return 0; }();
class NumArray {
public:
    NumArray(vector<int> nums) {
        sumnums = nums;
    }
    
    int sumRange(int i, int j) {
        return accumulate(sumnums.begin()+i, sumnums.begin()+j+1, 0);
    }
private:
    vector<int> sumnums;
};

int main()
{
    vector<int> vec = {-2, 0, 3, -5, 2, -1};
    NumArray *A = new NumArray(vec);
    cout << A->sumRange(0, 2);
    
    return 0;
}

 

 

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

static int x = []() {std::ios::sync_with_stdio(false); cin.tie(0); return 0; }();
class NumArray {
public:
    NumArray(vector<int> nums) {
        for(int i = 1; i < nums.size(); ++i){
            nums[i] += nums[i-1];
        }
        sumnums = nums;
    }
    
    int sumRange(int i, int j) {
        if(i == 0)
            return sumnums[j];
        return sumnums[j] - sumnums[i-1];
    }
private:
    vector<int> sumnums;
};

int main()
{
    vector<int> vec = {-2, 0, 3, -5, 2, -1};
    NumArray *A = new NumArray(vec);
    cout << A->sumRange(0, 2);
    
    return 0;
}

 

 

上面是accumulate()下面是for循环

template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init)
{
  while (first!=last) {
    init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
    ++first;
  }
  return init;
}

时间复杂度同是O(n)，耗时差这么多。