What are prefix and

The prefix and refers to the sum (including itself) of all elements of an array before a certain index. Prefix sums are divided into one-dimensional prefix sums and two-dimensional prefix sums. Prefix sum is an important preprocessing, which can reduce the time complexity of the algorithm.

What is a one-dimensional prefix sum?

Sum [I] = sum[i-1] + arr[I]; Sum is prefix and array, and arr is content array. With prefixes and arrays, we can solve for the sum of intervals in order one.

Interval [I, j] = sum[j] -sum [i-1]

And are subarrays of K

Given an array of integers and an integer k, you need to find the number of contiguous subarrays of that array and k.

Example 1: Input :nums = [1,1,1], k = 2 Output: 2, [1,1] and [1,1] are two different cases.Copy the code

Description:

  • The length of the array is [1, 20,000].
  • The range of the elements in the array is [-1000, 1000], and the range of the integer k is [-1e7, 1e7].
Idea 1: Use prefixes and

Firstly, the prefix and array are constructed by iterating through the number group. After having the prefix and array, the interval sum between each sub-item in the array and the previous sub-item is calculated through a double-layer loop (the sum of the sub-array). The time complexity is O(n^2).

/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number}* /
var subarraySum = function(nums, k) {
    const pre = []
    let count = 0
    
    // Build prefixes and arrays
    for (let i = 0; i < nums.length; i++) {
        const a = nums[i]
        const b = pre[i - 1= = =undefined ? 0 : pre[i - 1]
        pre[i] = a + b
    }

    // Use the prefix and to get interval sums quickly
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j <= i; j++) {
            Count + 1 = count + 1
            let intervalSum;
            if (j === 0) {
                intervalSum = pre[i]
            } else if (j === i) {
                intervalSum = nums[i]
            } else {
                intervalSum = pre[i] - pre[j - 1]}if (intervalSum === k) {
                count += 1}}}return count
};
Copy the code
Idea 1(optimization): Use prefixes and + hashes

If you just use prefixes and, the time complexity is still too high. Cannot pass all test cases and will time out. Let’s use hash tables to reduce time complexity.

To be honest with you, it took me a long time to figure out what to do with prefixes and hashes. Let me explain

We know that the interval sum is equal to k = sum[j] -sum [i-1], and we can obtain the formula sum[i-1] = sum[j] -k by simple transposition. When we iterate over nums, we get the current prefix sum, subtract k from the current prefix sum, we get the size of the other prefix sum we need to find, and if there are records in the hash, we just get the records in the hash, and we know how many interval sums are equal to k.


/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number}* /
 var subarraySum = function(nums, k) {
    let count = 0
    let preSum = 0
    let hash = {}

    for (let i = 0; i < nums.length; i++) {
        preSum += nums[i]
        const key = preSum - k
        if (hash[key]) {
           count += hash[key]
        }
        if (preSum === k) {
            count += 1
        }

        // Record the prefix and the number of occurrences
        if(! hash[preSum]) { hash[preSum] =1
        } else {
            hash[preSum] += 1}}return count
};
Copy the code

What is a two-dimensional prefix sum?

What is a two-dimensional prefix sum? The two-dimensional prefix sum is actually the prefix sum of the two-dimensional array. The calculation process of the two-dimensional prefix sum is as follows:

const arr = [
    [1.1.1],
    [1.1.1],
    [1.1.1]]PreSum [0, 0] = arr[0, 0]
PreSum [0, j] = preSum[0, j-1] + arr[0, j]
PreSum [I -1, 0] = preSum[I -1, 0] + arr[I, 0]
// Other cases. = 0 i ! = 0 preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + src[i][j] - preSum[i - 1][j - 1];

const preSum = [[], [], []]

for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[0].length; j++) {
        if (i == 0 && j == 0) {
            preSum[i][j] = arr[i][j]
        } else if (i == 0) {
            preSum[i][j] = preSum[i][j - 1] + arr[i][j]
        } else if (j == 0) {
            preSum[i][j] = preSum[i - 1][j] + arr[i][j]
        } else {
            preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + arr[i][j] - preSum[i - 1][j - 1]}}}// preSum[[1.2.3],
    [2.4.6],
    [3.6.9]]Copy the code

Two dimensional region and retrieval – matrix immutable

You can think of it as a sum of two dimensional arrays

Given a two-dimensional matrix, compute the sum of the elements within the range of its subrectangles, the upper left corner of which is (Row1, COL1) and the lower right corner of which is (Row2, col2).

The upper left corner (Row1, COL1) = (2, 1) and the lower right corner (Row2, COL2) = (4, 3) of the submatrix above, the sum of the elements in this subrectangle is 8.

Example:

A given matrix = [[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]] sumRegion (2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12Copy the code
Train of thought

First, find the corresponding 2d prefix and array. Take a look at the picture below:

If we want to find the sum of the regions from vertex A to point B, we can use the following method

sumRegion(A,B) = preSum(O,B) - preSum(O,C) - preSum(O,D) + preSum(O,E)

Recursive formula:

sumRegion(row2, col2, row1, Col1) = preSum[row2][COL2] − preSum[Row1 −1][COL2] + preSum[Row1 −1][COL1 −1]

We need to take extra care when row2, col2, row1, col1 is equal to 0, and we add one extra edge, one extra column to the prefix sum to avoid a lot of boundary condition judgments.

The formula becomes:

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

/ * * *@param {number[][]} matrix* /
 var NumMatrix = function(matrix) {
    / / the original matrix
    this.matrix = matrix
    // Prefix and matrix
    this.preSum = null

    if (matrix.length === 0 || matrix[0].length === 0) {
        return
    }
    
    // Build prefixes and matrices
    this.preSum = []
    for (let i = 0; i < this.matrix.length; i++) {
        this.preSum.push([])
    }
    for (let i = 0; i < this.matrix.length; i++) {
        for (let j = 0; j < this.matrix[0].length; j++) {
            if (i == 0 && j == 0) {
                this.preSum[i][j] = this.matrix[i][j]
            } else if (i == 0) {
                this.preSum[i][j] = this.preSum[i][j - 1] + this.matrix[i][j]
            } else if (j == 0) {
                this.preSum[i][j] = this.preSum[i - 1][j] + this.matrix[i][j]
            } else {
                this.preSum[i][j] = this.preSum[i - 1][j] + this.preSum[i][j - 1] + this.matrix[i][j] - this.preSum[i - 1][j - 1]}}}// Prefix and matrix add an extra row and column
    // Add a column
    for (let i = 0; i < this.preSum.length; i++) {
        this.preSum[i].unshift(0)}// Add a line
    this.preSum.unshift(new Array(this.preSum[0].length).fill(0))};/ * * *@param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}* /
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    if (this.preSum) {
        return this.preSum[row2 + 1][col2 + 1] + this.preSum[row1][col1] - this.preSum[row2 + 1][col1] - this.preSum[row1][col2 + 1]}return null
};

/** * Your NumMatrix object will be instantiated and called as such: * var obj = new NumMatrix(matrix) * var param_1 = obj.sumRegion(row1,col1,row2,col2) */
Copy the code