給定一個整型數組nums,找出在索引i到j(i小於等於j)之間(包括i和j)的所有元素之和。
例如:
給定nums = [-2,0,3,-5,2,-1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
批注:
你可以假定這個數組不會改變。
這裡會有很多次對sumRange函數的調用。
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:
You may assume that the array does not change.
There are many calls to sumRange function.
一開始我還以為這個題有多簡單呢,就寫了下面這個代碼:
class NumArray {
public:
vector numArray;
NumArray(vector &nums) {
numArray = nums;
}
int sumRange(int i, int j) {
int sum = 0;
while (i < j) {
sum += numArray[i++];
}
return sum;
}
};
因為不知道需要構造函數干嘛,所以硬生生的加了這麼一句進去,其實完全沒用。功能是實現了,但是面對題目變態的測試用例,果然還是崩了。
至於題目測試用例有多變態,數據來說話:一共214513個字符,其中包括了nums的數據,也包括了函數調用,nums的長度沒去算,但是sumRange函數的調用次數高達10000次。
看到這個測試用例,就明白要針對函數調用做優化,一個不錯的辦法是將所有的返回的值:
從0到1的所有元素之和,
從0到2的所有元素之和,
從0到10000的所有元素之和,
………………
然後計算i和j之間所有元素之和的時候,(因為包含了i和j),也就是求從0到j的所有元素之和減去從0到i-1的所有元素之和。
所以代碼就如下所示了,但是時間上還是使用了624ms叻。
class NumArray {
public:
map rangeSum;
NumArray(vector &nums) {
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
rangeSum.insert(pair(i, sum));
}
}
int sumRange(int i, int j) {
return rangeSum[j] - rangeSum[i - 1];
}
};
雖然對底層的具體實現不是很了解,但因為有索引,所以我自覺用vector的話查找其值來跟快速;而且添加值也更加快速,因為只是一個值而不用是鍵值對。
具體代碼如下:
class NumArray {
public:
vector rangeSum;
NumArray(vector &nums) {
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
rangeSum.push_back(sum);
}
}
int sumRange(int i, int j) {
return rangeSum[j] - rangeSum[i - 1];
}
};