力扣labuladong一刷day17天前綴和數組

一、303. 區域和檢索 - 數組不可變

題目鏈接：https://leetcode.cn/problems/range-sum-query-immutable/
思路：本題即為讓寫一個類用于計算指定區間內的數字和，但如果直接采用for循環的方式，當有很多的輸入實例時，會有很多的重復計算，非常浪費時間。
既然是計算區間和的值，那么我們可以提前準備一個前綴和數組，如nums=[a, b, c, d] 前綴和數組為preSum = [a, a+b, a+b+c, a+b+c+d]，這樣以后再計算區間和只需要使用前綴合數組preSum[right]-preSum[left]即可，這樣就把時間復雜度降低到了常量級。是一個不錯的小技巧。

class NumArray {int[] preSum;public NumArray(int[] nums) {this.preSum = new int[nums.length+1];for (int i = 1; i < preSum.length; i++) {preSum[i] = preSum[i-1] + nums[i-1];}}public int sumRange(int left, int right) {return preSum[right+1] - preSum[left];}
}

二、304. 二維區域和檢索 - 矩陣不可變

題目鏈接：https://leetcode.cn/problems/range-sum-query-2d-immutable/
思路：這兩道前綴和的題目讓我收益匪淺，使用前綴和的數組提前計算數組，把時間復雜度降低到O(1)。要想搞清楚前綴和數組，首先要在使用之前把定義明確，本題求二維區域和，定義前綴和數組為：preSum[i][j]為nums數組從區間[0,0]到[i-1, j-1]。明確定義后寫遞推公式，和動態規劃的dp數組特別像， preSum[i][j] = preSum[i-1][j] + preSum[i][j-1]+matrix[i-1][j-1] - preSum[i-1][j-1];
我感覺本題其實就是動態規劃的應用。

class NumMatrix {int[][] preSum;public NumMatrix(int[][] matrix) {int m = matrix.length, n = matrix[0].length;this.preSum = new int[m+1][n+1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {preSum[i][j] = preSum[i-1][j] + preSum[i][j-1]+matrix[i-1][j-1] - preSum[i-1][j-1];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return preSum[row2+1][col2+1] + preSum[row1][col1] - preSum[row2+1][col1] - preSum[row1][col2+1];}
}