1314. Matrix Block Sum

Link

Solution

先求出rangeSum

      int[][] rangeSum = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n ; j++){
                rangeSum[i][j] = rangeSum[i-1][j] + rangeSum[i][j-1] - rangeSum[i-1][j-1] + mat[i-1][j-1]; 
            }
        }

再透過rangeSum求出block sum

      int[][] ans = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                
                int r1 = Math.max(0, i-K);
                int r2 = Math.min(m-1, i+K);
                int c1 = Math.max(0, j-K);
                int c2 = Math.min(n-1, j+K);
                r1++;r2++;c1++;c2++; //rangeSum start from 1
                ans[i][j] = rangeSum[r2][c2] - rangeSum[r1-1][c2] - rangeSum[r2][c1-1] + rangeSum[r1-1][c1-1];
            }
        }
        return ans;