LeetCode-307 Range Sum Query

题目描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

题目大意

实现两个操作：更新数组，求数组范围内数字之和。

示例

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

解题思路

保存一个vector数组，更新时以O（1）时间复杂度更新，求和时以O（N）时间复杂度遍历数组求和。

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

代码

class NumArray {
public:
    NumArray(vector<int>& nums) {
        for(int n : nums)
            num.push_back(n);
    }
    
    void update(int i, int val) {
        num[i] = val;
    }
    
    int sumRange(int i, int j) {
        int sum = 0;
        for(int k = i; k <= j; ++k)
            sum += num[k];
        return sum;
    }
    
private:
    vector<int> num;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */