5-line C++ DP solution, O(n) space and O(1) time per query


  • 0
    class NumArray {
    public:
        NumArray(vector<int> &nums) {
            int sum = 0;
            for(auto it:nums)
                sums.push_back(sum+=it);
        }
        
        int sumRange(int i, int j) {
            return sums[j]- (i>0?sums[i-1]:0);
        }
    private:
        vector<int> sums;
    };

Log in to reply
 

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