303. Range Sum Query - Immutable

發表於 | 分類於

problem

solution

  • brute forces
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumArray {
private:
    vector<int> nums;
public:
    NumArray(vector<int>& nums) {
        //  -2  0   3   -5  2   -1
        this->nums = nums;
    }
    
    int sumRange(int left, int right) {
        // brute force
        int ret = 0;
        for(int i=left;i<=right;i++) ret+=nums[i];
        return ret;
    }
};

  • prefix sum
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class NumArray {
    private:
        vector<int> preSum;
    public:
        NumArray(vector<int>& nums) {
            //  -2  0   3   -5  2   -1
            //   0 -2  -2  1   -4  -2  -3
            int n = nums.size();
            preSum = vector<int>(n+1,0);
            for(int i=1;i<n+1;++i){
                preSum[i] = preSum[i-1] + nums[i-1];     
            }
        }
        int sumRange(int left, int right) {
            return preSum[right+1] - preSum[left];
        }
    };

    analysis

  • sumRange 函數 time complexity O(1)