Range Sum Query - Immutable

缺乏、安全感 2022-05-14 12:35 156阅读 0赞

# 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:**

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++示例 ##

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示例 ##

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) } }