【算法专题】前缀和（附图解、代码）

📑前言

本文主要是前缀和的文章，如果有什么需要改进的地方还请大佬指出⛺️

🎬作者简介：大家好，我是青衿🥇

☁️博客首页：CSDN主页放风讲故事

🌄每日一句：努力一点，优秀一点

在这里插入图片描述

class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        int n = words.length;
        int[] prefixSums = new int[n];
        prefixSums[0] = isVowelString(words[0]) ? 1 : 0;
        for (int i = 1; i < n; i++) {
            int value = isVowelString(words[i]) ? 1 : 0;
            prefixSums[i] = prefixSums[i - 1] + value;
        }
        int q = queries.length;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            int start = queries[i][0], end = queries[i][1];
            if(start == 0) {
                ans[i] = prefixSums[end];
                continue;
            }
            ans[i] = prefixSums[end] - prefixSums[start - 1];
        }
        return ans;
    }

    public boolean isVowelString(String word) {
        return isVowelLetter(word.charAt(0)) && isVowelLetter(word.charAt(word.length() - 1));
    }

    public boolean isVowelLetter(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

2.二维区域和检索 – 矩阵不可变

leetcode304

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化

int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

示例 1：

在这里插入图片描述

输入:

[“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”]

[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]

输出:

[null, 8, 11, 12]

解释:

NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);

numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)

numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)

numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length

n == matrix[i].length

1 <= m, n <= 200

-105 <= matrix[i][j] <= 105

0 <= row1 <= row2 < m

0 <= col1 <= col2 < n

最多调用 104 次 sumRegion 方法

思路：

1，二维前缀和，初始化preSum[0][0],以及第0行preSum[0][i]和第0列preSum[i][0]

2.从1，1开始遍历求出矩形的所有元素之和，即 preSum[i][j] = 左边前缀和+上面前缀和-左上角前缀和 + matrix[i][j];

3.注意preSum[i][j]的定义，以及左上角 (row1, col1) 、右下角 (row2, col2)

在这里插入图片描述

代码如下：

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