所有奇数长度子数组的和
解题思路：
-
创建长度为 n + 1 的前缀和数组 prefixSums，其中 prefixSums[0]=0，当 1≤i≤n 时，prefixSums[i] 表示数组 arr 从下标 0 到下标 i - 1 的元素和；
-
得到前缀和数组 prefixSums 之后，对于 0 ≤ start ≤ end < n，数组 arr 的下标范围 [start,end] 的子数组的和为 prefixSums[end+1]−prefixSums[start]，可以在 O(1) 的时间内得到每个子数组的和；
图解：
复杂度：
-
时间复杂度：O(n^2)，其中 n 是数组 arr 的长度，需要 O(n) 的时间计算前缀和数组 prefixSums，长度为奇数的子数组的数量是 O(n^2)，对于每个子数组需要 O(1) 的时间计算子数组的和，因此总时间复杂度是 O(n^2)；
-
空间复杂度：O(n)，其中 n 是数组 arr 的长度，需要创建长度为 n + 1 的前缀和数组 prefixSums；
代码实现：
var sumOddLengthSubarrays = function (arr) {
const n = arr.length;
const prefixSums = new Array(n + 1).fill(0);
// 前缀和
for (let i = 0; i < n; i++) {
prefixSums[i + 1] = prefixSums[i] + arr[i];
}
let sum = 0;
for (let start = 0; start < n; start++) {
for (let length = 1; start + length <= n; length += 2) {
const end = start + length - 1;
sum += prefixSums[end + 1] - prefixSums[start];
}
}
return sum;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
1385.两个数组间的距离值
上一篇
评论
