5-lines C++, 4-lines Python


  • 34

    The idea is fairly straightforward: create an array accu that stores the accumulated sum for nums such that accu[i] = nums[0] + ... + nums[i - 1] in the initializer of NumArray. Then just return accu[j + 1] - accu[i] in sumRange. You may try the example in the problem statement to convince yourself of this idea.

    The code is as follows.


    C++

    class NumArray {
    public:
        NumArray(vector<int> &nums) {
            accu.push_back(0);
            for (int num : nums)
                accu.push_back(accu.back() + num);
        }
    
        int sumRange(int i, int j) {
            return accu[j + 1] - accu[i];
        }
    private:
        vector<int> accu;
    };
    
    
    // Your NumArray object will be instantiated and called as such:
    // NumArray numArray(nums);
    // numArray.sumRange(0, 1);
    // numArray.sumRange(1, 2); 
    

    Python

    class NumArray(object):
        def __init__(self, nums):
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            self.accu = [0]
            for num in nums: 
                self.accu += self.accu[-1] + num,
    
        def sumRange(self, i, j):
            """
            sum of elements nums[i..j], inclusive.
            :type i: int 
            :type j: int
            :rtype: int 
            """
            return self.accu[j + 1] - self.accu[i]
    
    
    # Your NumArray object will be instantiated and called as such:
    # numArray = NumArray(nums)
    # numArray.sumRange(0, 1)
    # numArray.sumRange(1, 2)

  • 0
    S

    why does this line work to extend the array? self.accu += self.accu[-1] + num
    Is it a Python 2 treatment, I can't replicate in Python 3


  • 0
    G

    I saw this trick in a different post. You're missing a comma at the end of the line:

    self.accu += self_accu[-1] + num,
    

    That actually changes the assignment value to be a tuple (iterable) and therefore extends the array.


  • 2

    I think

    self.accu += [self.accu[-1] + num]
    

    is more readable


  • 0
    S

    got it, thanks!


  • 0

    @All Haha, in fact I learnt this line from Stefan and I now get used to using it since it saves some typings :-) Anyway, peisi's way is more readable.


  • 0
    C

    how about use partial_sum here ?


Log in to reply
 

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