Range Sum Query - Immutable

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.

 

 

Hide Company Tags

 

 

 解法一：

O(1) init, O(n) query

public class NumArray { private int[] nums; private int sum; public NumArray(int[] nums) { this.nums = nums; this.sum = 0; } public int sumRange(int i, int j) { sum = 0; //保证immutable for(int k = i;k<=j;k++) { sum = sum + nums[k]; } return sum; } } // Your NumArray object will be instantiated and called as such: // NumArray numArray = new NumArray(nums); // numArray.sumRange(0, 1); // numArray.sumRange(1, 2);

 

解法二：

O(n) init, O(1) query

public class NumArray { int[] nums; public NumArray(int[] nums) { for(int i = 1; i < nums.length; i++) nums[i] += nums[i - 1]; this.nums = nums; } public int sumRange(int i, int j) { if(i == 0) return nums[j]; return nums[j] - nums[i - 1]; } }

 reference: https://discuss.leetcode.com/topic/29194/java-simple-o-n-init-and-o-1-query-solution

转载于:https://www.cnblogs.com/hygeia/p/5703004.html

相关资源：JAVA上百实例源码以及开源项目