【数组】剑指 Offer II 012. 左右两边子数组的和相等 | 剑指 Offer II 013. 二维子矩阵的和

剑指 Offer II 012. 左右两边子数组的和相等

原题链接：
左右两边子数组的和相等

题目：
给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例：

输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

1 <= nums.length <= 104
-1000 <= nums[i] <= 1000

题解：
// 利用一个性质， 中心元素＋左边的元素和＋右边元素和，就等于数组所有元素和

class Solution {
    
public:
    int pivotIndex(vector<int>& nums) {
    
        int n = nums.size();
        if (n <= 0) return -1;
        
        int total = 0;
        for (int i = 0; i < n; ++i)
        {
    
            // 表示数组元素总合
            total += nums[i];
        }

        int sum = 0; // 表示一边的元素和
        for (int i = 0; i < n; ++i)
        {
    
            if (nums[i] + sum * 2 == total) {
    
                return i;
            }
            sum += nums[i];
        }

        return -1;
    }
};

剑指 Offer II 013. 二维子矩阵的和

原题链接：二维子矩阵的和

题目：

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

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

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

输入:
[“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 (蓝色矩形框的元素总和)

题解：一维前缀和

实现NumMatrix()函数，对二维数组先进行一维前缀和，保存在sums中。

创建 m 行 n+1 列的二维数组 sums，其中 m 和 n 分别是矩阵 matrix 的行数和列数，sums[i] 为 matrix[i] 的前缀和数组。将 sums 的列数设为 n+1 的目的是为了方便计算每一行的子数组和：

class NumMatrix {
    
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
    
        int m = matrix.size();
        if (m > 0) {
    
            int n = matrix[0].size();
            sums.resize(m, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
    
                for (int j = 0; j < n; j++) {
    
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
    
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
    
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }
};

题解：二维前缀和

将 sums 的行数和列数分别设为 m+1 和 n+1 的目的是为了方便计算 sumRegion(row1,col1,row2,col2)，不需要对 row1​=0 和 col1​=0 的情况特殊处理。此时有：

sumRegion(row1,col1,row2,col2) = sums[row2+1][col2+1] − sums[row1][col2+1] − sums[row2+1][col1] + sums[row1][col1]

class NumMatrix {
    
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
    
        int m = matrix.size();
        if (m > 0) {
    
            int n = matrix[0].size();
            sums.resize(m + 1, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
    
                for (int j = 0; j < n; j++) {
    
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
    
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
};

模板

// 预处理前缀和数组
{
    
    sum.resize(n+1, vector<int>(m+1,0));
    // 预处理除前缀和数组（模板部分)
    for(int i = 1; i <= n; i++) {
    
        for(int j = 1; j <= m; j++) {
    
            // 当前格子(和) = 上方的格子(和) + 左边的格子(和) - 左上角的格子(和) + 当前格子(值)【和是指对应的前缀和，值是指原数组中的值】
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
        }
    }
}
    
// 首先我们要令左上角为 (x1, y1) 右下角为 (x2, y2)
// 计算 (x1, y1, x2, y2) 的结果
{
    
    // 前缀和是从 1 开始，原数组是从 0 开始，上来先将原数组坐标全部 +1，转换为前缀和坐标
    x1++; y1++; x2++; y2++;
    // 记作 22 - 12 - 21 + 11，然后 不减，减第一位，减第二位，减两位
    // 也可以记作 22 - 12(x - 1) - 21(y - 1) + 11(x y 都 - 1)
    ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];

}