LeetCode link: 303. Range Sum Query - Immutable, difficulty: Easy.
Given an integer array nums, handle multiple queries of the following type:
- Calculate the sum of the elements of
numsbetween indicesleftandrightinclusive whereleft <= right.
Implement the NumArray class:
NumArray(int[] nums)Initializes the object with the integer arraynums.int sumRange(int left, int right)Returns the sum of the elements ofnumsbetween indicesleftandrightinclusive (i.e.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 (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^50 <= left <= right < nums.length- At most
10^4calls will be made tosumRange.
Intuition
Webmaster (Zhang Jian): π
Hi everyone! I am Zhang Jian.
I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed
leader.me!
π leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.
- Use a new array
prefix_sumsto save the sum of the previous elements. - The first element of
prefix_sumsis0because the prefix sum does not include the current element. - To find the
sumof the elements from indexlefttoright(inclusive), just useprefix_sums[right + 1] - prefix_sums[left].
Complexity
Time complexity
O(N)
Space complexity
O(N)
Java #
class NumArray {
private int[] prefixSums;
public NumArray(int[] nums) {
prefixSums = new int[nums.length + 1];
var sum = 0;
for (var i = 0; i < nums.length; i++) {
sum += nums[i];
prefixSums[i + 1] = sum;
}
}
public int sumRange(int left, int right) {
return prefixSums[right + 1] - prefixSums[left];
}
}
Python #
class NumArray:
def __init__(self, nums: List[int]):
self.prefix_sums = [0]
sum_ = 0
for num in nums:
sum_ += num
self.prefix_sums.append(sum_)
def sumRange(self, left: int, right: int) -> int:
return self.prefix_sums[right + 1] - self.prefix_sums[left]
C++ #
class NumArray {
private:
vector<int> prefixSums;
public:
NumArray(vector<int>& nums) {
prefixSums.push_back(0);
auto sum = 0;
for (auto num : nums) {
sum += num;
prefixSums.push_back(sum);
}
}
int sumRange(int left, int right) {
return prefixSums[right + 1] - prefixSums[left];
}
};
JavaScript #
let prefixSums
var NumArray = function (nums) {
prefixSums = [0]
let sum = 0
nums.forEach((num) => {
sum += num
prefixSums.push(sum)
})
};
NumArray.prototype.sumRange = function (left, right) {
return prefixSums[right + 1] - prefixSums[left]
};
C# #
public class NumArray
{
int[] prefixSums;
public NumArray(int[] nums)
{
prefixSums = new int[nums.Length + 1];
int sum = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
prefixSums[i + 1] = sum;
}
}
public int SumRange(int left, int right)
{
return prefixSums[right + 1] - prefixSums[left];
}
}
Go #
type NumArray struct {
prefixSums []int
}
func Constructor(nums []int) NumArray {
prefixSums := make([]int, len(nums) + 1)
sum := 0
for i, num := range nums {
sum += num
prefixSums[i + 1] = sum
}
return NumArray{prefixSums}
}
func (this *NumArray) SumRange(left int, right int) int {
return this.prefixSums[right + 1] - this.prefixSums[left]
}
Ruby #
class NumArray
def initialize(nums)
@prefix_sums = [0]
sum = 0
nums.each do |num|
sum += num
@prefix_sums << sum
end
end
def sum_range(left, right)
@prefix_sums[right + 1] - @prefix_sums[left]
end
end
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 303. Range Sum Query - Immutable. Thanks!Level Up Your Developer Identity
π While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend leader.me β the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- π Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
- π Free Custom Domain: Bind your own personal domain for freeβforever.
- β¨ Premium Subdomains: Stand out with elite tech handle like
name.leader.me.
Intuition of solution 2: Directly Returning the Sum of the Array Range (Slow)
Webmaster (Zhang Jian): π
Hi everyone! I am Zhang Jian.
I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed
leader.me!
π leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.
Directly returning the sum of the values ββin the array range can pass the test, but it will fail if the test case is stricter.
So we still need to learn a more efficient solution: Prefix Sum solution.
Complexity
Time complexity
O(M * N)
Space complexity
O(M * N)
Python #
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])
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 303. Range Sum Query - Immutable. Thanks!Level Up Your Developer Identity
π While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend leader.me β the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- π Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
- π Free Custom Domain: Bind your own personal domain for freeβforever.
- β¨ Premium Subdomains: Stand out with elite tech handle like
name.leader.me.