-
Notifications
You must be signed in to change notification settings - Fork 0
/
range_sum_query_immutable.py
38 lines (28 loc) · 1.06 KB
/
range_sum_query_immutable.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
"""
Task:
Given an integer array nums, handle multiple queries of the following type:
Calculate the sum of the elements of nums 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 nums between indices left and right inclusive
(i.e. nums[left] + nums[left + 1] + ... + nums[right]).
"""
from typing import List
# Solution 1 (slow)
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
def sumRange(self, l: int, r: int) -> int:
ans = 0
for i in range(l, r + 1):
ans += self.nums[i]
return ans
# Solution 2 (faster)
class NumArray:
def __init__(self, nums: List[int]):
self.preSum = nums
for i in range(len(nums)-1):
self.preSum[i+1] += self.preSum[i]
def sumRange(self, l: int, r: int) -> int:
if l == 0: return self.preSum[r]
return self.preSum[r] - self.preSum[l-1]