
Description
The problem involves implementing a class NumArray
that can efficiently calculate the sum of elements in a given range of an integer array. The class should have a constructor that initializes the array and a method sumRange(left, right)
that returns the sum of elements between the indices left
and right
(inclusive).
Intuition
The straightforward way to calculate the sum of elements between two indices is to iterate through the array from left
to right
and accumulate the sum. This approach is simple and intuitive but may not be the most efficient for repeated queries.
Approach
- Initialization: Store the array
nums
when initializing theNumArray
object. - Calculate Range Sum: The
sumRange
method iterates through the array elements from indexleft
toright
and computes the sum. This method provides a direct solution to calculate the sum in the specified range. - Optimization Considerations: While this approach is straightforward, it may be inefficient for large arrays with frequent sum queries. To optimize, we might consider preprocessing the array to enable faster range sum queries (e.g., using a prefix sum array), but this is not covered in the current implementation.
Complexity
Time Complexity:
The time complexity for each sumRange
query is (O(n)), where (n) is the number of elements between left
and right
. This linear time complexity could be a drawback for large arrays with many queries.
Space Complexity:
The space complexity is (O(1)) beyond the space required to store the input array nums
. No additional space is used apart from the input array.
Code
C++
class NumArray {
public:
NumArray(std::vector& nums) {
this->nums = nums;
}
int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; ++i) {
sum += nums[i];
}
return sum;
}
private:
std::vector nums;
};
Python
class NumArray:
def __init__(self, nums):
self.nums = nums
def sumRange(self, left, right):
return sum(self.nums[left:right+1])
Java
public class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += nums[i];
}
return sum;
}
}
JavaScript
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
var NumArray = function(nums) {
this.nums = nums;
};
NumArray.prototype.sumRange = function(left, right) {
let sum = 0;
for(let i = left; i <= right; i++) sum += this.nums[i]
return sum
};