题目

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

  1. Given nums = [-2, 0, 3, -5, 2, -1]
  3. sumRange(0, 2) -> 1
  4. sumRange(2, 5) -> -1
  5. sumRange(0, 5) -> -3

Note:

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

题意

给定一个数组，求从下标i到j的元素之和。

思路

因为方法可能被多次调用，因而可以用缓存进行优化：另设数组sum，sum[i]表示nums中前i个元素之和。因此i到j的元素之和就可以表示为sum[j + 1] - sum[i]。

代码实现

Java

  1. class NumArray {
  2.     private int[] sum;
  4.     public NumArray(int[] nums) {
  5.         sum = new int[nums.length + 1];
  6.         for (int i = 0; i < nums.length; i++) {
  7.             sum[i + 1] = sum[i] + nums[i];
  8.         }
  9.     }
  11.     public int sumRange(int i, int j) {
  12.         return sum[j + 1] - sum[i];
  13.     }
  14. }