LeetCode #303. Range Sum Query

时间:2022-04-28 22:18:50

问题:

Given an integer array nums, find the sum of the elements between indices i and j (ij), 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.

题目大意:

自己构造一个类,构造函数传入一数组,求和函数给一个起始下标,一个终止下标,求这个闭区间的和。

初始思路:

类中有一个数组,构造函数把传入的数组赋值给类的数组。

求和时从起始下标开始遍历至终止下标。

class NumArray {
public:
NumArray(vector<int> &nums) {
arr = nums;
} int sumRange(int i, int j) {
int sum = 0;
while (i <= j)
{
sum += arr[i];
i++;
}
return sum;
}
private:
vector<int> arr;
};

这种思路中,复杂度为O(j-i)(O(n))题目中说sum函数会频繁调用,复杂度不好,结果是超时。

改进思路:

因为频繁的使用sum函数,需要降低该函数的复杂度。降低的方法从构造函数入手,使得类内的数组存着sum值,这样可以得到复杂度O(1)的sum函数。

class NumArray {
public:
NumArray(vector<int> &nums) {
arr.push_back(0);
for (int i = 1; i<=nums.size(); i++)
arr.push_back(arr[i - 1] + nums[i-1]);
} int sumRange(int i, int j) {
return (arr[j + 1] - arr[i]);
}
vector<int> arr;
};

这段代码的关键在构造函数,这里类中的arr数组下标i存的是nums数组前i-1个元素的和。每次将前一个sum元素加num元素得到一个sum元素追加到尾部,相当于遍历了一遍num数组,构造函数的复杂度是O(n)。值得注意的是,采用一般的思路时,构造函数的复杂度也是O(n)。

总结

这道题看起来非常简单,即使初学者也可完成,但想要降低复杂度就需要一个巧妙的算法。

题目中自己编写的代码不知是一个求和函数,而是一个类(包括构造函数),这应该是一个很强的提示,要利用只调用一次的构造函数,去降低sum函数的复杂度。

题目另一个提示就是There are many calls to sumRange function.这也体现了需要降低sum函数复杂度的需求。

这是本人第一道leetcode题目,以后要加油啊~