README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Easy	https://github.com/doocs/leetcode/edit/main/solution/1500-1599/1588.Sum%20of%20All%20Odd%20Length%20Subarrays/README_EN.md	1408	Biweekly Contest 35 Q1	Array Math Prefix Sum

1588. Sum of All Odd Length Subarrays

中文文档

Description

Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.

A subarray is a contiguous subsequence of the array.

 

Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66

 

Constraints:

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

 

Follow up:

Could you solve this problem in O(n) time complexity?

Solutions

Solution 1

Python3

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ans, n = 0, len(arr)
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += arr[j]
                if (j - i + 1) & 1:
                    ans += s
        return ans

Java

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += arr[j];
                if ((j - i + 1) % 2 == 1) {
                    ans += s;
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += arr[j];
                if ((j - i + 1) & 1) {
                    ans += s;
                }
            }
        }
        return ans;
    }
};

Go

func sumOddLengthSubarrays(arr []int) (ans int) {
	n := len(arr)
	for i := range arr {
		s := 0
		for j := i; j < n; j++ {
			s += arr[j]
			if (j-i+1)%2 == 1 {
				ans += s
			}
		}
	}
	return
}

TypeScript

function sumOddLengthSubarrays(arr: number[]): number {
    const n = arr.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        let s = 0;
        for (let j = i; j < n; ++j) {
            s += arr[j];
            if ((j - i + 1) % 2 === 1) {
                ans += s;
            }
        }
    }
    return ans;
}

Rust

impl Solution {
    pub fn sum_odd_length_subarrays(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut ans = 0;
        for i in 0..n {
            let mut s = 0;
            for j in i..n {
                s += arr[j];
                if (j - i + 1) % 2 == 1 {
                    ans += s;
                }
            }
        }
        ans
    }
}

C

int sumOddLengthSubarrays(int* arr, int arrSize) {
    int ans = 0;
    for (int i = 0; i < arrSize; ++i) {
        int s = 0;
        for (int j = i; j < arrSize; ++j) {
            s += arr[j];
            if ((j - i + 1) % 2 == 1) {
                ans += s;
            }
        }
    }
    return ans;
}