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.


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


    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

    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

    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

    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

    how about use partial_sum here ?

  • 0

    In python, itertools.accumulate() does this faster and shorter.

Log in to reply

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