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.

**Understand the problem:**

For the naive solution, each time we call the sumRange(lo, hi), we sum up the numbers and return the result. So the time complexity would be O(n).

Note that there are many calls to sumRange function, so we can calculate the prefix sum in the constructor. Then each time we call the sumRange(lo, hi), we just need to calculate the prefix[hi] - prefix[lo - 1], in O(1) time.

**Code (Java):**

public class NumArray { private int[] nums; public NumArray(int[] nums) { this.nums = nums; // Calculate the prefix sum for (int i = 1; i < nums.length; i++) { nums[i] += nums[i - 1]; } } public int sumRange(int i, int j) { if (i < 0 || i >= nums.length || j < 0 || j >= nums.length || i > j) { return 0; } if (i == 0) { return nums[j]; } else { return nums[j] - nums[i - 1]; } } }

## No comments:

## Post a Comment