A rough AC C++ solution, DP


  • 0
    class NumArray {
    	vector<int> A;
    public:
    	NumArray(vector<int> &nums) 
    	{
    		if (nums.empty())
    			return;
    		int sz = nums.size();
    		vector<int> t(sz, 0);
    		A = t;
    		A[0] = nums[0];
    		int i;
    		for (i = 1; i < sz; ++i)
    			A[i] = A[i - 1] + nums[i];
    	}
    
    	int sumRange(int i, int j) 
    	{
    		if (A.empty())
    			return 0;
    		if (0 == i)
    			return A[j];
    		else
    			return A[j] - A[i - 1];
    	}
    };
    

    To make this code more concise, I have made some revises. Use A.back() and A.push_back() to replace A = t.

    class NumArray {
    	vector<int> A;
    public:
    	NumArray(vector<int> &nums) 
    	{
    		A.push_back(0);
    		for (auto x : nums)
    			A.push_back(x + A.back());
    	}
    
    	int sumRange(int i, int j) 
    	{
    		return A[j + 1] - A[i];
    	}
    };

Log in to reply
 

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