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
所有奇数长度子数组的和。
给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题有一个复杂度为 O(n) 的思路,但是如果没做过,面试的时候几乎不会想到。这里我暂时提供一个前缀和的思路。
首先我们用一个数组记录一下 input 数组的前缀和,然后我需要用两层 for 循环,第一层枚举的是子数组的长度,应该只有奇数;第二层枚举的是子数组左端点的下标。
时间O(n^2)
空间O(n)
Java实现
1 class Solution { 2 public int sumOddLengthSubarrays(int[] arr) { 3 int[] presum = new int[arr.length + 1]; 4 for (int i = 0; i < arr.length; i++) { 5 presum[i + 1] = presum[i] + arr[i]; 6 } 7 8 int res = 0; 9 // 枚举子数组长度 10 for (int i = 1; i <= arr.length; i += 2) { 11 // 枚举左端点 12 for (int j = 0; j + i - 1 < arr.length; j++) { 13 res += presum[j + i] - presum[j]; 14 } 15 } 16 return res; 17 } 18 }