GuoXin Li's Blog

LeetCode 303. Range Sum Query - Immutable

LeetCode
字数统计: 270阅读时长: 1 min
2020/02/26 Share

303. Range Sum Query - Immutable

303. Range Sum Query - Immutable

Description

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class NumArray {
    int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++){
            sum[i+1] = sum[i] + nums[i];        //S(n) = S(n-1) + f(n);
        }
    }

    public int sumRange(int i, int j) {
        return sum[j+1] - sum[i];               //S(n+2) - S(n) = f(n+1) + f(n+2);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */
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

/**
 * C++
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */
class NumArray {
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        if (n==0) return;
        sum_ = vector<int> (n, 0);
        sum_[0] = nums[0];
        for (int i=1;i<nums.size();i++){
            sum_[i] = sum_[i-1] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        if(i==0) return sum_[j];
        return sum_[j] - sum_[i-1];
    }
private:
    vector<int> sum_;
};

image-20200226224942382

Time Complexity: Query$O(1)$ Pre-calculate $O(n)$

Space Complexity: $O(n)$

CATALOG
  1. 1. 303. Range Sum Query - Immutable
  2. 2. Description
  3. 3. Example:
Total : 89
2022
2021
2020
2019
2018
essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
Machine-Learning Data-Structure