This is the daily problem of 2021-8-29 on LeetCoded: “1588. Sum of all Odd-length subarrays”

1. Topic description

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

2. Answer

Firstly, the prefix sum of each position of the array is calculated by in-situ modification according to “1480. Dynamic sum of one-dimensional array”, and then the sum of all odd-length subarrays is calculated by determining the left and right boundaries.

Use a double for loop to determine the left and right boundaries I and j, with the outer I +1 each time, and the inner j +2 each time because the subarray length is odd.

For example, for the use case arr = [1,4,2,5,3], notice that at this point arr is already prefixed with the sum of the input array:

• i ! = 0, such as[I, j] = [1, 3]Subarray of intervals,2,5 [4], and forarr[3] - arr[1-1], i.e.,arr[j] - arr[i-1]
• i == 0, such as[I, j] = [0, 2]Subarray of intervals,4,2 [1], and forarr[2], i.e.,arr[j]
• So the sum up is, for[i,j]Interval subarray of, and arearr[j] - (arr[i - 1] || 0)
• Loop summing up the subarray sum of the interval

const sumOddLengthSubarrays = arr= > {
    const len = arr.length;
    // Modify in place, calculate the prefix and
    for (let i = 1; i < len; i++) {
        arr[i] += arr[i - 1];
    }
    // Define the return value, starting with 0
    let res = 0;
    // Define the left boundary
    for (let i = 0; i < len; i++) {
        // Define the right boundary, because the length is odd, j +2 each time
        for (let j = i; j < len; j += 2) {
            // at this point arr is already the prefix sum
            // i! ==0, the sum of the length in the interval [I,j] = arr[j] -arr [i-1]
            // I ===0, [j] = arr[j]
            res += arr[j] - (arr[i - 1] | |0); }}return res;
};
Copy the code

---

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”