[Leetcode]303.区域和检索304.二维区域和检索

简单题，前缀和方法

乍一看就觉得应该用前缀和来做，一个数组多次查询。

实现方法: 新建一个private数组prefix_sum[i]，用来存储nums前i个数组的和，

需要找区间和的时候直接通过prefix_sum[j]-prefix[i-1]即可得到从[i,j]区间的和，当i是0的时候需要特殊处理以防数组越界。

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