303. 区域和检索 – 数组不可变

303. 区域和检索 - 数组不可变

Difficulty: 简单

给定一个整数数组  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 方法。

Solution 1. Brute Force

​class NumArray {
public:
    NumArray(vector<int>& nums) {
        m_vec = nums;
    }

    int sumRange(int i, int j) {
        int count = 0;
        for(int a = i; a<=j; ++a){
            count += m_vec[a];
        }
        return count;
    }
private:
    vector<int> m_vec;
};

思路

别说了，渣渣只有这种想法，但是我居然通过，说好的超时呢？

solution 2. 前缀和

class NumArray {
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        m_prefixSum.resize(n+1);
        m_prefixSum[0] = 0;
        for(int i = 0; i<n ; ++i){
            m_prefixSum[i + 1] = m_prefixSum[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return m_prefixSum[j + 1] - m_prefixSum[i];
    }
private:
    vector<int> m_prefixSum;
};

思路

前缀和，对于sum(i,j)之间的计算可以转换为sum(0,j+1)的和sum(0,i)之差。而后者可以在一开始就计算出来。