[关闭]
@Yano 2016-03-21T12:31:10.000000Z 字数 781 阅读 2001

LeetCode 303 Range Sum Query - Immutable

LeetCode


题目描述

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:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

分析

题目中描述,函数可能被调用很多次,并且函数是不可变的。那么可以构造一个数组sum,sum[i] 存放数组 nums从 0 到 i 的和,这样能在 O(1) 的复杂度内求出指定范围的和。

代码

  1. public class NumArray {
  2. public long[] sum;
  3. public NumArray(int[] nums) {
  4. sum = new long[nums.length + 1];
  5. for (int i = 0; i < nums.length; i++) {
  6. sum[i + 1] += nums[i] + sum[i];
  7. }
  8. }
  9. public int sumRange(int i, int j) {
  10. if (i > j || i < 0 || j >= sum.length - 1) {
  11. return Integer.MIN_VALUE;
  12. }
  13. return (int) (sum[j + 1] - sum[i]);
  14. }
  15. }
  16. // Your NumArray object will be instantiated and called as such:
  17. // NumArray numArray = new NumArray(nums);
  18. // numArray.sumRange(0, 1);
  19. // numArray.sumRange(1, 2);
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注