Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/303.html
Given an integer array nums
, handle multiple queries of the following type:
- Calculate the sum of the elements of
nums
between indicesleft
andright
inclusive 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 ofnums
between indicesleft
andright
inclusive (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] <= 105
0 <= left <= right < nums.length
- At most
104
calls will be made tosumRange
.
Algorithm
Establish a cumulative sum array dp, where dp[i]
represents the sum of the numbers in the interval [0, i]
, then [i,j]
can be expressed as dp[j]-dp[i-1]
, pay attention here When i=0, just return dp[j]
directly.
Code
-
public class Range_Sum_Query_Immutable { class NumArray { private int[] sum; public NumArray(int[] nums) { sum = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { // sum x meaning sumup until index x-1 sum[i + 1] = sum[i] + nums[i]; } } public int sumRange(int i, int j) { return sum[j + 1] - sum[i]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(i,j); */ } ############ 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) { dp.resize(nums.size() + 1, 0); for (int i = 1; i <= nums.size(); ++i) { dp[i] = dp[i - 1] + nums[i - 1]; } } int sumRange(int i, int j) { return dp[j + 1] - dp[i]; } private: vector<int> dp; };
-
''' >>> 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 = new 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 = new 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->sum = [0]; for ($i = 0; $i < count($nums); $i++) { array_push($this->sum, $this->sum[$i] + $nums[$i]); } } /** * @param Integer $left * @param Integer $right * @return Integer */ function sumRange($left, $right) { return $this->sum[$right + 1] - $this->sum[$left]; } }
-
struct NumArray { sums: 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 sums = vec![0; n + 1]; for i in 0..n { sums[i + 1] = sums[i] + nums[i]; } Self { sums } } fn sum_range(&self, left: i32, right: i32) -> i32 { self.sums[(right + 1) as usize] - self.sums[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); */