303. Range Sum Query - Immutable.md

303. Range Sum Query - Immutable

---

leetcode-cn Daily Challenge on March 1st.

---

Difficulty : Easy

Related Topics : Dynamic Programming

---

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.

---

Solution

• mine
  • Java
    • Prefix Sum Runtime: 22 ms, faster than 27.71%, Memory Usage: 46.3 MB, less than 10.60% of Java online submissions

      //init:O(N)time   sumRange:O(1)time
      //init:O(N)space   sumRange:O(1)space
      int[] sums;
      public NumArray(int[] nums) {
          sums = new int[nums.length + 1];
          for(int i = 1; i < sums.length; i++){
              sums[i] = sums[i - 1] + nums[i - 1];
          }
      }
      
      public int sumRange(int i, int j) {
          return sums[j + 1] - sums[i];
      }
      

---