LeetCode
September 7, 2018

Range Sum Query - Immutable

303. Range Sum Query - Immutable

题目描述

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

Example:

1
2
3
4
5
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.

思路分析

题目中提示给定的nums数组不变，而且sumRange()函数可能需要多次被调用。

这个就很简单了，我们计算出来当前位置元素到初始元素之间所有元素之和，并进行存储，每次需要求解给定区间元素之和的时候收尾相减即可。这样就可以大大减少调用多次sumRange()函数的计算时间。

注意：我们的和元素组成的数组中第一个元素是0。

其实，我觉得这道题并不完全能算得上一道动态规划的题目。但是LeetCode把这道题归类到动态规划中也说得过去吧。

C++示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumArray {
private:
    vector<int> sums;
public:
    NumArray(vector<int> nums) {
        sums.push_back(0);
        for (int i = 0; i < nums.size(); ++i) {
            sums.push_back(nums[i] + sums[i]);
        }
    }

    int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
};

int main() {
    vector<int> nums{-2, 0, 3, -5, 2, -1};
    NumArray obj(nums);
    int result = obj.sumRange(2, 5);
    cout << result << endl;
    return 0;
}

Scala示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object RangeSumQuery {

  class NumArray(nums: Array[Int]) {

    private val sums = new Array[Int](nums.length + 1)
    for (i <- nums.indices)
      sums(i + 1) = sums(i) + nums(i)

    def sumRange(i: Int, j: Int): Int = {
      sums(j + 1) - sums(i)
    }
  }

  def main(args: Array[String]): Unit = {
    val nums = Array(-2, 0, 3, -5, 2, -1)
    val obj = new NumArray(nums)
    val result = obj.sumRange(2, 5)
    println(result)
  }
}