C++ DP O(1) in space with explanation


  • 0
    T

    We calculate the value of sum from 0 to position i right when we receive the table.
    The value of sum from i to j is then:
    num[j] - num[i-1] if i > 0
    otherwise if i ==0 then we just need to return the position j in the table.

        NumArray(vector<int> nums): num(nums) {
            for (int i=1; i < num.size(); i++){
                num[i] = num[i] + num[i-1];
            }
        }
        
        int sumRange(int i, int j) {
            if (i==0) return num[j];
            return num[j]-num[i-1];
        }
    

Log in to reply
 

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