Title: Range Sum Query – Immutable Source: leetcode.com
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
|
1 2 3 4 5 |
Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 |
Note:
- You may assume that the array does not change.
- There are many calls to sumRange function.
Python solution
|
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 |
''' https://leetcode.com/problems/range-sum-query-immutable/ ''' class NumArray(object): def __init__(self, nums): """ initialize your data structure here. :type nums: List[int] """ self.numbers = nums self.sums = [] p = 0 for c in nums: self.sums.append(c + p) p += c def sumRange(self, i, j): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ if i == 0: return self.sums[j] return self.sums[j] - self.sums[i] + self.numbers[i] # 16/16 # 92 ms |