C++ Solution: O(n) time complexity for initialization and O(1) time complexity for query


  • 0
    Y
    class NumArray {
    public:
        NumArray(vector<int> &nums) {
            if(!nums.size())
                return ;
            sum.resize(nums.size());
            sum[0] = nums[0]; 
            for(int i = 1; i < nums.size(); ++ i)
                sum[i] = nums[i] + sum[i - 1];
        }
    
        int sumRange(int i, int j) {
            if(!sum.size())
                return 0;
            int sum_i = 0, sum_j = 0;
            if(i)
                sum_i = sum[i - 1];
            sum_j = sum[j];
            return sum_j - sum_i;
        }
    private:
    vector<int> sum;
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.