303. Range Sum Query - Immutable

  • 27.2%

https://leetcode.com/problems/range-sum-query-immutable/

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

1
2
3
4
5
6
Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

cpp


https://discuss.leetcode.com/topic/29206/5-lines-c-4-lines-python

5-lines C++, 4-lines Python

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

https://discuss.leetcode.com/topic/30269/c-o-1-queries-just-2-extra-lines-of-code

C++ O(1) queries - just 2 extra lines of code

1
2
3
4
5
6
7
8
9
10
11
12
class NumArray {
public:
NumArray(vector<int> &nums) : psum(nums.size()+1, 0) {
partial_sum( nums.begin(), nums.end(), psum.begin()+1);
}

int sumRange(int i, int j) {
return psum[j+1] - psum[i];
}
private:
vector<int> psum;
};

python


https://discuss.leetcode.com/topic/29226/a-very-short-python-solution

A very short Python solution

1
2
3
4
5
6
7
8
class NumArray(object):
def __init__(self, nums):
self.dp = nums
for i in xrange(1, len(nums)):
self.dp[i] += self.dp[i-1]

def sumRange(self, i, j):
return self.dp[j] - (self.dp[i-1] if i > 0 else 0)

java


https://discuss.leetcode.com/topic/29194/java-simple-o-n-init-and-o-1-query-solution

Java simple O(n) init and O(1) query solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class NumArray {

int[] nums;

public NumArray(int[] nums) {
for(int i = 1; i < nums.length; i++)
nums[i] += nums[i - 1];

this.nums = nums;
}

public int sumRange(int i, int j) {
if(i == 0)
return nums[j];

return nums[j] - nums[i - 1];
}
}
谢谢你,可爱的朋友。