題目：
給定一個整數陣列 nums，求出陣列從索引 i 到 j（i ≤ j）范圍內元素的總和，包含 i、j 兩點，
實作 NumArray 類：
NumArray(int[] nums) 使用陣列 nums 初始化物件
int sumRange(int i, int j) 回傳陣列 nums 從索引 i 到 j（i ≤ j）范圍內元素的總和，包含 i、j 兩點（也就是 sum(nums[i], nums[i + 1], … , nums[j])）
示例：
輸入：
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
輸出：
[null, 1, -1, -3]
解釋：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
提示：
0 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= i <= j < nums.length
最多呼叫 104 次 sumRange 方法
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/range-sum-query-immutable
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
首先作為萌新，第一個想到的就是暴力解法，直接利用for回圈將下標 i 到 j 的每一項全部加起來，但是時間復雜度每次都是O(n)，反復呼叫花費的時間會特別多，
因此嘗試在暴力解法的基礎上進行優化，因為陣列是固定不變的，如果說在創建類內部陣列的時候進行前綴和計算，最后求 i 到 j 范圍內元素的總和只需要利用對應前綴和求差進行運算就可以了，
原始陣列
| -2 | 0 | 3 | -5 | 2 | -1 |
|---|
前綴和陣列（首位未添加0）
| -2 | -2 | 1 | -4 | -2 | -3 |
|---|
不過因為求出陣列從索引 i 到 j（i ≤ j）范圍內元素的總和時是包含 i、j 兩點，因此在這里需要考慮 i=0 的情況，可以使用 if 進行處理，不過事后看了題解，嘗試在前綴和陣列首添加一位0會更加方便求解，
前綴和陣列
| 0 | -2 | -2 | 1 | -4 | -2 | -3 |
|---|
這個時候會發現，求出陣列從索引 i 到 j（i ≤ j）范圍內元素的總和（包含 i、j 兩點），只需要用 sums[j+1]-sums[i] 即可，
代碼
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(sums[i]+nums[i]);
}
}
int sumRange(int i, int j) {
return sums[j+1]-sums[i];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/265494.html
標籤：其他
下一篇：Unity 簡單的傷害數字顯示