Accepted c++ but a bit slow (588ms) any suggestions?


  • 0
    S
     class NumArray {
     private:
    	 vector<int> sums = vector<int>();
    	 vector<int> _nums;
     public:
    	 NumArray(vector<int> &nums) {
    		 _nums = nums;
    		 if(_nums.size() != 0)
    		 sums.push_back(_nums[0]);
    	 }
    	 int sumRange(int i, int j) {
    		 if (sums.size()-1 < j)
    		 {
    			 for (int s = sums.size(); s <= j; ++s)
    				 sums.push_back( sums.back() + _nums[s]);
    		 }
    		 return sums[j] - (i-1>=0 ? sums[i-1] : 0);
    	 }
     };

  • 0
    Q

    I think I figured out the answer. It should be due to the "push_back()" function of the vector type that is causing the slowness of C++ solution.

    The "pushback()" method will check if the pre-allocated array has enough space. If not, it will increase the vector length by 2x and then copy all the old vector element to the new allocated vector, pushback the newly added element, and then delete the old vector. This process will take a long time.

    Unlike other languages, say, Java, the API uses int[] array. The size of the array is fixed and the accessing of the array is pretty fast. No "push_back" action is required.


Log in to reply
 

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