leetcode Question: Range Sum Query - Immutable

Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
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.

Analysis:

This is a simple DP problem. By just watching the example, we could easily find the solution:

nums = [-2, 0, 3, -5, 2, -1]

For each index i we could compute the sum from 0 to i:

sum = [-2, -2+0, -2+0+3, -2+0+3-5, -2+0+3-5+2, -2+0+3-5+2-1]

Therefore, if we want to find the sum between i and j:

  • sum[ i ] can be viewed as sum[ 0 to i ]
  • sum[ j ] can be viewed as sum[ 0 to j ]
  • sum[ i-1 ] + sum[ i to j ] = s[ 0 to j ]
  • sum [ i to j ] = sum[ j ] - sum[ i-1 ]

Code (C++):

class NumArray {
public:
NumArray(vector<int> &nums) {
sums = nums;
for (int i = 1; i< nums.size(); i++){
sums[i] = sums[i-1] + nums[i];
}
}
int sumRange(int i, int j) {
return i==0 ? sums[j] : sums[j] - sums[i-1];
}
private:
vector<int> sums;
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

Code (Python):

class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
self.sums = nums[:]
for i in range(1, len(self.sums)):
self.sums[i] = self.sums[i-1] + nums[i]
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]
else:
return self.sums[j] - self.sums[i-1]
# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.sumRange(1, 2)

1 comment:

  1. This website can live streaming , you can join at my site :
    agen judi online terpercaya
    Prediksi Bola

    Thank you
    agenpialaeropa.net
    gamesonline.ga
    beritasemasaterikini.com

    ReplyDelete