This is the 29th day of my participation in the August Wenwen Challenge.More challenges in August

Topic describes

This is 1588 on LeetCode. Sum of all odd-length subarrays, difficulty is easy.

Tag: “prefix and”, “math”

Given an array of positive integers, arr, ask you to calculate the sum of all possible odd-length subarrays.

A subarray is defined as a continuous subsequence of the original array.

Return the sum of all odd-length subarrays in arR.

Example 1:

Input: arr = [1,4,2,5,3] output: 58 explanation: all odd-length subarrays and their sum are: [1] [4] = 1 = 4 [5] [2] = 2 = 5,4,2 [1] [3] = 3 = 7,2,5 [4] = 11,5,3 [2] = 10,4,2,5,3 [1] = 15 we sum all the values get 1 + 4 + 2 + 5 Plus 3 plus 7 plus 11 plus 10 plus 15 is 58Copy the code

Example 2:

Input: arr = [1,2] Output: 3 Explanation: There are only two odd length subarrays, [1] and [2]. They add up to 3.Copy the code

Example 3:

Arr = [10,11,12] output: 66Copy the code

Tip:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000

The prefix and

Enumerating all subarrays of odd length can be done by a two-level loop of “Enumerating length – enumerating the left end point, and counting the right end point”.

[l,r][L,r][l, r][l,r] [l,r][l, r][l,r] [l,r][L,r][L,r][L,r][L,r][L,r][L,r][L,r][L,r][L,r][L,r][L,r]

For such interval summation problems, we should think of “prefix sum” optimization: preprocessing prefixes and arrays with O(n)O(n)O(n) complexity, each query [L,r][L,r][L,r] interval sum can be returned in O(1)O(1)O(1) O(1).

Code:

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i - 1];
        int ans = 0;
        for (int len = 1; len <= n; len += 2) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                ans += sum[r + 1] - sum[l]; }}returnans; }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n)O(n)O(n)

mathematics

In fact, we can count the number of occurrences of any single arr[I]arr[I] in an odd subarray.

For any position III in the original array, there are a total of iii numbers on the left and n− I − 1N-I-1N − I −1 numbers on the right.


a r r [ i ] arr[i] The necessary and sufficient condition for being a member of an odd subarray is that the number of elements on the left and right sides of the odd subarray is the same.

Therefore, the problem is transformed into how to obtain “the number of schemes where arr[I]arr[I]arr[I] has an odd number of consecutive elements in the left segment of the original array” and “the number of schemes where arr[I]arr[I] has an even number of consecutive elements in the right segment of the original array”.

Since we already know that arr[I]arr[I] has a total of III numbers on the left and n− I − 1n-i-1N − I −1 numbers on the right, we can calculate the combination number:

  • The number of schemes for odd numbers on the left of position III is (I +1)/2(I +1)/2(I +1)/2, and the number of schemes for odd numbers on the right is (N − I)/2(N-i)/2(n − I)/2.
  • location
    i i     The number of schemes with even (non-zero) numbers on the right is
    i / 2 i / 2     , the number of schemes with even (non-zero) numbers on the right is
    ( n – i – 1 ) / 2 (n – i – 1) / 2     ;

    • Considering the number of legitimate even number alternatives without selecting the left and right sides, the number of even number alternatives increases by 111 on the basis of the above analysis.

So far, we have obtained the number of odd and even schemes around position iii. According to “if arr[I]arr[I]arr[I] is in an odd subarray, the number of elements on the left and right sides of arr[I] is the same” and “the multiplication principle”, We know how many odd subarrays arr[I]arr[I] occurs in, and then multiply arr[I]arr[I]arr[I] is the contribution of arr[I]arr[I] to the answer.

Code:

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l1 = (i + 1) / 2, r1 = (n - i) / 2; / / odd
            int l2 = i / 2, r2 = (n - i - 1) / 2; / / even
            l2++; r2++;
            ans += (l1 * r1 + l2 * r2) * arr[i];
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1588 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.