leetcode 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.

题目大意：给定一个数组，返回小标[i, j]的元素之和。

用途：在窗口一定大小时，做滑动平均。可用于图像中的均值滤波

思路一：每次给定[i, j]，直接计算。

 1 class NumArray {
 2 private:
 3     vector<int> sum;
 4 public:
 5     NumArray(vector<int>& nums) {
 6         sum = nums;
 7     }
 8
 9     int sumRange(int i, int j) {
10         int ans = 0;
11         for (int k = i; k <= j; ++k) {
12             ans += sum[k];
13         }
14         return ans;
15     }
16 };

思路二：

sum[k] 记录 [0,k]的累加和，计算下标[i, j]的元素和为sum[j] - sum[i - 1], k = 0时，sum[0] = nums[0];

 1 class NumArray {
 2 private:
 3     vector<int> sum;
 4 public:
 5     NumArray(vector<int>& nums) {
 6         sum.assign(nums.begin(), nums.end());
 7         for (int i = 1; i < nums.size(); ++i) {
 8             sum[i] = sum[i - 1] + nums[i];
 9         }
10     }
11
12     int sumRange(int i, int j) {
13         if (i == 0) return sum[j];
14         return sum[j] - sum[i - 1];
15     }
16 };