[Algorithm Selection] Prefix and Special Topic – Three

Article directory

  • Foreword
  • [Subarray whose sum is K](https://leetcode.cn/problems/subarray-sum-equals-k/description/)
    • Title description
    • Think analysis
    • Code
  • [Subarray sums divisible by K](https://leetcode.cn/problems/subarray-sums-divisible-by-k/)
    • Title description
    • Problem-solving instructions:
    • Algorithm idea:
    • Code
  • [Contiguous array](https://leetcode.cn/problems/contiguous-array/submissions/)
    • Title description
    • Think analysis
    • Code
  • [Matrix area sum](https://leetcode.cn/problems/matrix-block-sum/)
    • Title description
    • Think analysis
    • Code
  • ?Summarize

Foreword

Meaning:

  • The prefix sum is actually for an array of length n. We create a new array of length n + 1, and the value of the i-th element is the sum of the previous i elements (including the i-th element) .

Features:

  1. The prefix sum array is one length longer than the original array.
  2. The value of the 0th element of the prefix sum is 0.
  3. According to the characteristics of prefix and array, find the prefix sum. We only need to use the value of the i-th element + the value of the i-1 prefix array to get the value of the i-th prefix sum array. (This is also a dynamic programming idea).

Application:

  • The prefix sum algorithm can solve some problems related to continuity in arrays

Subarray whose sum is K

Title description

Given an integer array nums and an integer k, please count and return the number of subarrays in the array whose sum is k.

A subarray is a contiguous, non-empty sequence of elements in the array.

  • Example 1:
    Input: nums = [1,1,1], k = 2
    Output: 2

  • Example 2:
    Input: nums = [1,2,3], k = 3
    Output: 2

class Solution {<!-- -->
    public int subarraySum(int[] nums, int k) {<!-- -->

    }
}

Analysis of ideas


Let i be any position in the array, sum[i] represents the sum of all elements in the range [0, i].

If you want to know how many “arrays that end with i and sum to k”, you need to find how many starting positions are x1, x2, x3… so that the sum of all elements in the [x, i] interval is k .

Then is the sum in the interval [0, x] equal to sum[i] – k? So the question becomes:

  • Just find how many prefix sums are equal to sum[i] – k in the interval [0, i – 1].

We don’t actually initialize the prefix sum array, because we only care about how many prefix sums are equal to sum[i] – k before position i. Therefore, we only need to create a hash table, one side to find the prefix sum of the current position, and one side to save the number of occurrences of each prefix sum before.

Code implementation

class Solution {<!-- -->
    public int subarraySum(int[] nums, int k) {<!-- -->
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(0, 1);
        int sum = 0;
        int ret = 0;
        for(int x : nums)
        {<!-- -->
            sum + = x; // Calculate the prefix sum of the current position
            ret + = hash.getOrDefault(sum - k, 0); // Statistical results
            hash.put(sum, hash.getOrDefault(sum, 0) + 1); // Throw the current prefix sum into the hash table
        }
        return ret;
    }
}

and a subarray divisible by K

Title description

Given an integer array nums and an integer k , return the number of (contiguous, non-empty) subarrays whose sum of elements is divisible by k .

A subarray is a contiguous portion of an array.

  • Example 1:
    Input: nums = [4,5,0,-2,-3,1], k = 5
    Output: 7
    explain:
    There are 7 subarrays such that the sum of their elements is divisible by k = 5:
    [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3 ], [-twenty three]

  • Example 2:
    Input: nums = [5], k = 9
    Output: 0

class Solution {<!-- -->
    public int subarraysDivByK(int[] nums, int k) {<!-- -->

    }
}

Problem-solving instructions:

  • Congruence Theorem

If (a – b) % n == 0, then we can get the following conclusion: a % n = = b % n.

The word description is that if the difference between two numbers is divisible by n, then the results of the two numbers modulo n are the same.

  • The result of negative number modulo in Java and how to correct the result of “negative number modulo”

Regarding the modulo operation of negative numbers in Java, the result is “treat the negative number as a positive number, and add a negative sign to the modulo result.”

For example: -1 % 3 = -(1 % 3) = -1

Because there are negative numbers, in order to prevent the occurrence of “negative numbers”, the output in the form of (a % n + n) % n is guaranteed to be positive.

For example: -1 % 3 = (-1 % 3 + 3) % 3 = 2

Algorithm idea:

The idea is similar to the question of Array whose sum is K

Let i be any position in the array, sum[i] represents the sum of all elements in the range [0, i].

  • If you want to know how many “arrays ending with i are divisible by k”, you need to find how many starting positions are x1, x2, x3… so that the sum of all elements in the interval [x, i] can be Divisible by k.

  • Assume that the sum of all elements in the interval [0, x – 1] is equal to a, and the sum of all elements in the interval [0, i] is equal to b, we can get (b – a) % k == 0.

  • According to the congruence theorem, the prefix sum in the interval [0, x – 1] is congruent with the interval [0, i]. So the question becomes:

    • Just find how many prefix sums have the remainder equal to sum[i] % k in the interval [0, i – 1].

We don’t actually initialize the prefix sum array, because we only care about how many prefix sums are equal to sum[i] – k before position i. Therefore, we only need to create a hash table, one side to find the prefix sum of the current position, and one side to save the number of occurrences of each prefix sum before.

Code implementation

class Solution {<!-- -->
    public int subarraysDivByK(int[] nums, int k) {<!-- -->
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(0 % k, 1);
        int sum = 0;
        int ret = 0;
        for(int x : nums)
        {<!-- -->
            sum + = x; // Calculate the prefix sum of the current position
            int r = (sum % k + k) % k;
            ret + = hash.getOrDefault(r, 0); // Statistical results
            hash.put(r, hash.getOrDefault(r, 0) + 1);
        }
        return ret;
    }
}

Continuous array

Title description

Given a binary array nums , find the longest contiguous subarray containing the same number of 0s and 1s, and return the length of the subarray.

  • Example 1:
    Input: nums = [0,1]
    Output: 2
    Explanation: [0, 1] is the longest contiguous subarray with the same number of 0s and 1s.

  • Example 2:
    Input: nums = [0,1,0]
    Output: 2
    Explanation: [0, 1] (or [1, 0]) is the longest contiguous subarray with the same number of 0s and 1s.

class Solution {<!-- -->
    public int findMaxLength(int[] nums) {<!-- -->

    }
}

Analysis of ideas

After a slight transformation, the next question will become a question we are familiar with:

  • This question asks us to find a continuous interval in which 0 and 1 appear the same number of times.

  • If 0 is recorded as -1 and 1 is recorded as 1, the problem becomes to find an interval whose sum is equal to 0.

  • So, the idea is the same as the question 560. Array whose sum is K


Let i be any position in the array, sum[i] represents the sum of all elements in the range [0, i].
If you want to know the final “array that ends with i and has a sum of 0”, you need to find the first x1 from left to right so that the sum of all elements in the [x1, i] range is 0. Then the sum in the interval [0, x1 – 1] is sum[i]. So the question becomes:

  • Just find the position where sum[i] appears for the ?th time in the interval [0, i – 1]. We don’t actually initialize the prefix sum array, because we only care about the position before position i, where the first prefix sum equals sum[i]. Therefore, we only need to create a hash table, one side to find the prefix sum of the current position, and the other side to record the position where the prefix sum appears for the first time.

Code implementation

class Solution {<!-- -->
    public int findMaxLength(int[] nums) {<!-- -->
        Map<Integer,Integer> hashmap = new HashMap<>();
        hashmap.put(0,-1);
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < nums.length; i + + ) {<!-- -->
            sum + = (nums[i] == 0 ? -1 : 1);
            if(hashmap.containsKey(sum)) {<!-- -->
                ret = Math.max(ret,i - hashmap.get(sum));
            } else {<!-- -->
                hashmap.put(sum,i);
            }
        }
        return ret;
    }
}

Matrix area sum

Title description

Given an m x n matrix mat and an integer k, please return a matrix answer, where each answer[i][j] is the sum of all elements mat[r][c] that satisfy the following conditions:

i – k <= r <= i + k, j - k <= c <= j + k and (r, c) are in the matrix.

  • Example 1:
    Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
    Output: [[12,21,16],[27,45,33],[24,39,28]]

  • Example 2:
    Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
    Output: [[45,45,45],[45,45,45],[45,45,45]]

class Solution {<!-- -->
    public int[][] matrixBlockSum(int[][] mat, int k) {<!-- -->

    }
}

Analysis of ideas

For a simple answer to the dimensional prefix sum, the key is that when we fill in the result matrix, we must find the coordinates of the “upper left” and “lower right” of the corresponding area of the original matrix (it is recommended to draw a picture)

Regarding the method of finding the two-dimensional prefix sum, if you don’t know Baozi, you can check and learn from the blogger’s “[Algorithm Selection] Prefix Sum Special Topic – One”

Upper left coordinate: x1 = i – k, y1 = j – k, but since it will “exceed the range of the matrix”, it is necessary to take a max for 0. Therefore, the corrected coordinates are: x1 = max(0, i – k), y1 = max(0, j – k);
Lower right coordinates: x1 = i + k, y1 = j + k, but since it will “exceed the range of the matrix”, it is necessary to take min for m- 1 and n – 1. Therefore, the corrected coordinates are: x2 = min(m – 1, i + k),
y2 = min(n – 1, j + k)

Then substitute the calculated coordinates into the calculation formula of “dimensional prefix sum matrix” (but pay attention to the mapping relationship of the subscripts)

Code implementation

class Solution {<!-- -->
    public int[][] matrixBlockSum(int[][] mat, int k) {<!-- -->
        int m = mat.length, n = mat[0].length;
        // 1. Preprocessing prefix sum matrix
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i + + ) {<!-- -->
            for (int j = 1; j <= n; j + + ) {<!-- -->
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1 ];
            }
        }
        // 2. Use?
        int[][] ret = new int[m][n];
        for(int i = 0; i < m; i + + ) {<!-- -->
            for (int j = 0; j < n; j + + ) {<!-- -->
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1;
                int y2 = Math.min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
}

?Summary

That’s all for the explanation of “[Algorithm Optimization] Prefixes and Topics – Three”. Thank you all for your support. You are welcome to leave messages, exchanges and criticisms. If the article is helpful to you or you think the author’s writing is good, you can click and follow. Like, support by collecting it!