[array] sword finger offer II 012 The sum of left and right subarrays is equal | sword finger offer II 013 Sum of two dimensional submatrix

The finger of the sword Offer II 012. The sum of the left and right subarrays is equal

Original link ：
The sum of the left and right subarrays is equal

subject ：
Give you an array of integers nums , Please calculate the of the array Center subscript .

Array Center subscript Is a subscript of the array , The sum of all elements on the left is equal to the sum of all elements on the right .

If the central subscript is at the leftmost end of the array , Then the sum of the numbers on the left is regarded as 0 , Because there is no element to the left of the subscript . This also applies to the fact that the central subscript is at the rightmost end of the array .

If the array has multiple central subscripts , Should return to Closest to the left The one of . If the array does not have a central subscript , return -1 .

Example ：

Input ：nums = [1,7,3,6,5,6]
Output ：3
explain ：
The central subscript is 3 .
The sum of the numbers on the left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
The sum of the numbers on the right sum = nums[4] + nums[5] = 5 + 6 = 11 , Two equal .

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

Answer key ：
// Use a property , The central element ＋ The elements on the left and ＋ Right element and , Is equal to the sum of all the elements of the array

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)
        {
    
            //  Represents the sum of array elements 
            total += nums[i];
        }

        int sum = 0; //  Elements representing one side and 
        for (int i = 0; i < n; ++i)
        {
    
            if (nums[i] + sum * 2 == total) {
    
                return i;
            }
            sum += nums[i];
        }

        return -1;
    }
};

The finger of the sword Offer II 013. Sum of two-dimensional submatrix

Original link ： Sum of two-dimensional submatrix

subject ：

Given a two-dimensional matrix matrix, Multiple requests of the following types ：

Calculate the sum of the elements in its subrectangle , The upper left corner of the submatrix is (row1, col1) , The lower right corner is (row2, col2) .

Realization NumMatrix class ：

NumMatrix(int[][] matrix) Given an integer matrix matrix To initialize
int sumRegion(int row1, int col1, int row2, int col2) Return to the upper left corner (row1, col1) 、 The lower right corner (row2, col2) The sum of the elements of the submatrix of .

Input :
[“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]]
Output :
[null, 8, 11, 12]
explain :
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 ( The sum of the elements of the red rectangle )
numMatrix.sumRegion(1, 1, 2, 2); // return 11 ( The sum of the elements of the green rectangle )
numMatrix.sumRegion(1, 2, 2, 4); // return 12 ( Sum of elements in blue rectangle )

Answer key ： One dimensional prefixes and

Realization NumMatrix() function , The two-dimensional array is prefixed with a one-dimensional prefix , Save in sums in .

establish m That's ok n+1 Two dimensional array of columns sums, among m and n These are matrices matrix The number of rows and columns ,sums[i] by matrix[i] Prefix and array . take sums Set the number of columns to n+1 The purpose of is to facilitate the calculation of subarray and ：

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;
    }
};

Answer key ： Two dimensional prefixes and

take sums The number of rows and columns of are set to m+1 and n+1 The purpose of is to facilitate the calculation sumRegion(row1,col1,row2,col2), No need. row1​=0 and col1​=0 Special treatment for special cases . At this time there is ：

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];
    }
};

Templates

//  Preprocessing prefixes and arrays 
{
    
    sum.resize(n+1, vector<int>(m+1,0));
    //  Preprocessing except prefixes and arrays （ The template section )
    for(int i = 1; i <= n; i++) {
    
        for(int j = 1; j <= m; j++) {
    
            //  Current grid ( and ) =  The upper grid ( and ) +  The left grid ( and ) -  The grid in the upper left corner ( and ) +  Current grid ( value )【 And refers to the corresponding prefix and , Value refers to the value in the original array 】
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
        }
    }
}
    
//  First, let's make the upper left corner  (x1, y1)  The lower right corner is  (x2, y2)
//  Calculation  (x1, y1, x2, y2)  Result 
{
    
    //  The prefix and are from  1  Start , The original array is from  0  Start , First, all the coordinates of the original array  +1, Convert to prefix and coordinates 
    x1++; y1++; x2++; y2++;
    //  Write it down as  22 - 12 - 21 + 11, then   No reduction , Minus the first , Minus second , Minus two digits 
    //  It can also be recorded as  22 - 12(x - 1) - 21(y - 1) + 11(x y  all  - 1)
    ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];

}