My solution, beat 56.7%


  • 0
    T
    class NumArray {
        vector<int>integralVec;
    public:
        NumArray(vector<int> &nums) {
            int sum = 0;
            vector<int>::iterator it=nums.begin();
            while(it!=nums.end())
            {
                sum+=*it;
                integralVec.push_back(sum);
                it++;
            }
            
        }
    
        int sumRange(int i, int j) {
            if(0==i){
                return integralVec.at(j);
            }else
            {
                return integralVec.at(j)-integralVec.at(i-1);
            }
        }
    };

  • 1
    S

    I reformatted the code and submitted many times, and the result of the same code varied from "beating" 82...15% so it is probably tested on busy server.

    As the vector is not changing, i chose to reuse it, so this solution should be faster, by not allocating memory and uses 50% of memory compared to most other solutions.

    class NumArray {
            int* const m_piSums;
        public:
        	NumArray(vector<int>& n) : m_piSums(&n[0]) { 
        	    int s = n.size();
        	    for (int i = 1; i < s; i++) {
        	        m_piSums[i] += m_piSums[i-1]; 
        	    }
        	}
            int sumRange(const int i, const int j) { 
                return m_piSums[j] - (i ? m_piSums[i - 1] : 0);
            }
        };
    

    or if you like shorter

    struct NumArray {
        int* p;
        NumArray(vector<int>& n) : p(&n[0]) { for (int i = 1; i < n.size(); i++) p[i] += p[i-1]; }
        int sumRange(int i, int j) { return p[j] - (i ? p[i - 1] : 0); }
    };

Log in to reply
 

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