LeetCode 303. Range Sum Query – Immutable

Description

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

Given an integer array nums, find the sum of the elements between indices left and right inclusive, where (left <= right).

Implement the NumArray class:

  • NumArray(int[] nums) initializes the object with the integer array nums.
  • int sumRange(int left, int right) returns the sum of the elements of the nums array in the range [left, right] inclusive (i.e., sum(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 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

Constraints:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= left <= right < nums.length
  • At most 104 calls will be made to sumRange.

Explanation

Just slice the list to do the sum.

Python Solution

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        
    def sumRange(self, left: int, right: int) -> int:
        
        return sum(self.nums[left : right + 1])


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.