1. 題目

給定一個整數數組 nums，求出數組從索引 i 到 j (i ≤ j) 范圍內元素的總和，包含 i, j 兩點。

示例： 給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數為 sumRange() sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3說明: 你可以假設數組不可變。 會多次調用 sumRange 方法。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/range-sum-query-immutable
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

進階題目：LeetCode 307. 區域和檢索 - 數組可修改（樹狀數組）

• 前綴和存儲起來，端點做差

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

32 ms 17.1 MB

總結

以上是生活随笔為你收集整理的LeetCode 303. 区域和检索 - 数组不可变（前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。