题目

类型：前缀和
image.png

解题思路

这道题的最优解法是使用前缀和将sumRange函数的时间复杂度降到O(1)，避免使用for循环

核心思路是我们new一个新的数组preSum出来，preSum[i]记录nums[0..i-1]的累加和

image.png

preSum 数组 ，如果想求得索引区间[1,4]内所有元素就可以通过preSum[5]-preSum[1]得出

代码

  1. class NumArray {
  3.     private int[] preSum;
  5.     public NumArray(int[] nums) {
  6.         preSum = new int[nums.length + 1];
  7.         for (int i = 1; i < preSum.length; i++){
  8.             preSum[i] = preSum[i - 1] + nums[i - 1];
  9.         }
  10.     }
  12.     public int sumRange(int left, int right) {
  13.         return preSum[right + 1] - preSum[left];
  14.     }
  15. }
  17. /**
  18.  * Your NumArray object will be instantiated and called as such:
  19.  * NumArray obj = new NumArray(nums);
  20.  * int param_1 = obj.sumRange(left,right);
  21.  */