Welcome to Subscribe On Youtube
303. Range Sum Query - Immutable
Description
Given an integer array nums, handle multiple queries of the following type:
- Calculate the sum of the elements of
numsbetween indicesleftandrightinclusive whereleft <= right.
Implement the NumArray class:
NumArray(int[] nums)Initializes the object with the integer arraynums.int sumRange(int left, int right)Returns the sum of the elements ofnumsbetween indicesleftandrightinclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
Input ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output [null, 1, -1, -3] Explanation NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1 numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1 numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 1050 <= left <= right < nums.length- At most
104calls will be made tosumRange.
Solutions
Solution 1: Prefix Sum
We create a prefix sum array $s$ of length $n + 1$, where $s[i]$ represents the prefix sum of the first $i$ elements, that is, $s[i] = \sum_{j=0}^{i-1} nums[j]$. Therefore, the sum of the elements between the indices $[left, right]$ can be expressed as $s[right + 1] - s[left]$.
The time complexity for initializing the prefix sum array $s$ is $O(n)$, and the time complexity for querying is $O(1)$. The space complexity is $O(n)$.
-
class NumArray { private int[] s; public NumArray(int[] nums) { int n = nums.length; s = new int[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } } public int sumRange(int left, int right) { return s[right + 1] - s[left]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */ -
class NumArray { public: NumArray(vector<int>& nums) { int n = nums.size(); s.resize(n + 1); for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } } int sumRange(int left, int right) { return s[right + 1] - s[left]; } private: vector<int> s; }; /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * int param_1 = obj->sumRange(left,right); */ -
''' >>> from itertools import accumulate >>> accumulate([1,2,3]) <itertools.accumulate object at 0x108f38340> >>> list(accumulate([1,2,3])) [1, 3, 6] >>> list(accumulate([1,2,3], initial=0)) [0, 1, 3, 6] >>> list(accumulate([1,2,3], initial=10)) [10, 11, 13, 16] ''' # note: when using python2, I always got error when importing it, via itertools.accumulate() # switching to python3, then all good for itertools.accumulate() class NumArray: def __init__(self, nums: List[int]): self.s = list(accumulate(nums, initial=0)) def sumRange(self, left: int, right: int) -> int: return self.s[right + 1] - self.s[left] # Your NumArray object will be instantiated and called as such: # obj = NumArray(nums) # param_1 = obj.sumRange(left,right) ############ class NumArray(object): def __init__(self, nums): """ initialize your data structure here. :type nums: List[int] """ self.dp = [0] * (len(nums) + 1) for i in range(0, len(nums)): self.dp[i + 1] = self.dp[i] + nums[i] def sumRange(self, i, j): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ return self.dp[j + 1] - self.dp[i] # Your NumArray object will be instantiated and called as such: # numArray = NumArray(nums) # numArray.sumRange(0, 1) # numArray.sumRange(1, 2) -
type NumArray struct { s []int } func Constructor(nums []int) NumArray { n := len(nums) s := make([]int, n+1) for i, v := range nums { s[i+1] = s[i] + v } return NumArray{s} } func (this *NumArray) SumRange(left int, right int) int { return this.s[right+1] - this.s[left] } /** * Your NumArray object will be instantiated and called as such: * obj := Constructor(nums); * param_1 := obj.SumRange(left,right); */ -
class NumArray { private s: number[]; constructor(nums: number[]) { const n = nums.length; this.s = Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { this.s[i + 1] = this.s[i] + nums[i]; } } sumRange(left: number, right: number): number { return this.s[right + 1] - this.s[left]; } } /** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(left,right) */ -
/** * @param {number[]} nums */ var NumArray = function (nums) { const n = nums.length; this.s = Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { this.s[i + 1] = this.s[i] + nums[i]; } }; /** * @param {number} left * @param {number} right * @return {number} */ NumArray.prototype.sumRange = function (left, right) { return this.s[right + 1] - this.s[left]; }; /** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(left,right) */ -
class NumArray { /** * @param Integer[] $nums */ function __construct($nums) { $this->s = [0]; foreach ($nums as $x) { $this->s[] = $this->s[count($this->s) - 1] + $x; } } /** * @param Integer $left * @param Integer $right * @return Integer */ function sumRange($left, $right) { return $this->s[$right + 1] - $this->s[$left]; } } /** * Your NumArray object will be instantiated and called as such: * $obj = NumArray($nums); * $ret_1 = $obj->sumRange($left, $right); */ -
struct NumArray { s: Vec<i32>, } /** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */ impl NumArray { fn new(mut nums: Vec<i32>) -> Self { let n = nums.len(); let mut s = vec![0; n + 1]; for i in 0..n { s[i + 1] = s[i] + nums[i]; } Self { s } } fn sum_range(&self, left: i32, right: i32) -> i32 { self.s[(right + 1) as usize] - self.s[left as usize] } }/** * Your NumArray object will be instantiated and called as such: * let obj = NumArray::new(nums); * let ret_1: i32 = obj.sum_range(left, right); */