Given an array of positive integers arr
, calculate the sum of all possible odd-length subarrays.
A subarray is a contiguous subsequence of the array.
Return the sum of all odd-length subarrays of arr
.
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
Solution 0: Brute Force
Enumerate all odd length subarrys: O(n^2), each take O(n) to compute the sum.
Total time complexity: O(n^3)
Space complexity: O(1)
Solution 1: Running Prefix Sum
Reduce the time complexity to O(n^2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int sumOddLengthSubarrays(vector<int>& arr) { const int n = arr.size(); int ans = 0; for (int i = 0, s = 0; i < n; ++i, s = 0) for (int j = i; j < n; ++j) { s += arr[j]; ans += s * ((j - i + 1) & 1); } return ans; } }; |
Solution 2: Math
Count how many times arr[i] can be in of an odd length subarray
we chose the start, which can be 0, 1, 2, … i, i + 1 choices
we chose the end, which can be i, i + 1, … n – 1, n – i choices
Among those 1/2 are odd length.
So there will be upper((i + 1) * (n – i) / 2) odd length subarrays contain arr[i]
ans = sum(((i + 1) * (n – i) + 1) / 2 * arr[i] for in range(n))
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 |
class Solution { public: int sumOddLengthSubarrays(vector<int>& arr) { const int n = arr.size(); int ans = 0; for (int i = 0; i < n; ++i) ans += ((i + 1) * (n - i) + 1) / 2 * arr[i]; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment