gogoWebsite

Table of contents

1. Prefix and algorithm

2. Prefix and implementation

Leetcode 303: Regions and Retrieval - Array Immutable

Leetcode 304: 2D intervals and retrieval - array immutable

Leetcode 560: Subarray of sum K

3. Summary

---

1. Prefix and algorithm

Definition of prefix sum: The sum of the array from the beginning to a specific position.

Through prefix and problems, we can calculate the sum of the values ​​of the array in a certain interval. The steps are as follows:

(1) Create a vector to store prefixes, and calculate the prefix sum at each position through a certain calculation method (see the subsequent examples for calculation).

(2) Calculate the sum of the numerical values ​​of a certain interval or region through a certain calculation method (see the subsequent examples for calculation).

2. Prefix and implementation

Leetcode 303: Region and Retrieval - Array Immutable

Title description:

Given an array of integers nums, calculate the sum of the values ​​between any two positions.

Ideas:

(1) The way to calculate the prefix sum is: sums[i] = sums[i-1] + nums[i-1], that is, the current prefix sum is equal to the sum of the prefix sum of the previous element and the value of the current element.

(2) The way to calculate the interval value is: res = sums[j+1] - sums[i], that is, the sum of the values ​​of the interval is equal to the difference between the sum of the prefixes of the two points.

Notice:

(1) Prefixes and generally start recording from the subscript of 1, that is, the second position. This is to prevent the cross-border problem caused by the lower bound of the interval being 0.

(2) The size of the vector needs to be defined in advance to prevent cross-border problems. (Use the resize function)

Code:

class NumArray {
public:
    vector<int>sums;
    NumArray(vector<int>& nums) {
        int n = ();
        (n+1);
        for(int i=1; i<=n; i++){
            sums[i] = sums[i-1]+nums[i-1];
        }
    }
    
    int sumRange(int left, int right) {
        return sums[right+1]-sums[left];

    }
};

Leetcode304: 2D intervals and retrieval - array immutable

Title description:

Given a two-dimensional matrixmatrix, calculate prefix sum, region numeric sum

Ideas:

(1) The way to calculate the prefix sum is: sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + nums[i-1][j-1]

(2) The way to calculate the sum of the region is: res = sums[x2+1][y2+1] - sums[x1][y2+1] - sums[x2+1][y1] + sums[x1][y1]

Notice:

(1) To prevent cross-border, all data of sums starts from the position with the subscript of 1.

(2) Due to changes in subscripts, please pay attention to whether +1 -1 is needed.

Code:

class NumMatrix {
 public:
     vector<vector<int>> sums;
     NumMatrix(vector<vector<int>>& matrix) {
         int m,n;
         m = (); //Line Number
         n = matrix[0].size(); //Number of columns
         (m+1,vector<int>(n+1));
         for(int i=1; i<=m; i++){
             for(int j=1; j<=n; j++){
                 sums[i][j] = sums[i-1][j] + sums[i][j-1]
                 - sums[i-1][j-1] + matrix[i-1][j-1];
             }
         }
     }
    
     int sumRegion(int row1, int col1, int row2, int col2) {
         return sums[row2+1][col2+1] - sums[row2+1][col1]
         - sums[row1][col2+1] + sums[row1][col1];
     }
 };

grammar:

(1) Find the number of rows of a two-dimensional vector: (); Find the number of columns of a two-dimensional vector: a[0].size()

(2) Redefine the size of a two-dimensional vector: (m+1, vector<int>(n+1))

Leetcode 560: Subarray of sum K

Title description:

Give you an array of integersnumsand an integerk, please count and returnThe array is neutralized ask The number of subarrays。

Ideas:

(1) Create a hash table (unordered_map) to record the prefix and occurrence times before the element.Set the value with the hash table key 0 to 1

(2) Iterate over the element once:

① Calculate the current prefix and

② Calculate the difference between the current prefix and the target value, and find the number of occurrences of the difference in hashmap (that is, the number of intervals that meet the conditions ending with the current traversal element)

Notice:

(1) The initialization of this question is very important! Since the prefix and default to 0 when there is no element, it must be set in advance.

Code:

class Solution {
 public:
     int subarraySum(vector<int>& nums, int k) {
         unordered_map<int,int> sums; //Record the number of occurrences of prefix sums that appear before the current element
         sums[0]=1; //Initialization
         int pre=0, res=0;
         for(int i=0; i<();i++){
             pre += nums[i];
             res += sums[pre-k];
             sums[pre]++;
         }
         return res;
     }
 };

3. Summary

The two important processes of prefix and algorithms are: calculating the prefix sum, using the prefix and calculating the value of a certain interval or region.

Three details to pay attention to are: prefix and array subscript, subscript correspondence, and array size determination

(1) When there is no element, the prefix sum defaults to 0, so in general, the array recording the prefix sum starts from where the subscript is 1 to prevent cross-border. This requires special attention to the correspondence between the original subscript and the prefix and subscript, and see if +1 or -1 is needed

(2) Note that the defined vector has no size, and resize it yourself to prevent cross-border

(3) In question 560, you need to traverse the elements and record the number of cases that are true under the condition that the current element is the upper bound. This requires the hash table to update the prefix and number that appear in time. Note that the hash table key is 0 and the value is 1.