【Leetcode】1588. Sum of All Odd Length Subarrays-白红宇

【Leetcode】1588. Sum of All Odd Length Subarrays

阅读量：240 次

发布时间：2019-02-28

本文共 1068 字，大约阅读时间需要 3 分钟。

为了求解所有长奇数的子数组的和的总和，我们可以采用前缀和数组加双层循环的方法。这种方法虽然时间复杂度为O(n²)，但对于大多数情况来说是有效且易于实现的。

步骤解析

计算前缀和数组：

创建一个前缀和数组preSum，其中preSum[i]表示数组A的前i个元素的和。通过遍历数组，逐个计算每个元素与前一个前缀和的和，得到前缀和数组。

遍历所有奇数长度的子数组：

外层循环遍历所有奇数长度，从1开始，每次增加2，直到数组长度。

内层循环遍历每个可能的起始点，确保子数组的长度为奇数，并计算对应子数组的和。

累加子数组的和：

对于每个奇数长度子数组，使用前缀和数组快速计算其和，并将其累加到结果中。

代码实现

public class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int[] preSum = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            preSum[i + 1] = preSum[i] + arr[i];
        }
        int res = 0;
        for (int i = 1; i <= arr.length; i += 2) {
            for (int j = 0; j + i - 1 < arr.length; j++) {
                res += preSum[j + i] - preSum[j];
            }
        }
        return res;
    }
}

代码解释

前缀和数组计算：

初始化preSum数组，长度为arr.length + 1。

遍历数组arr，计算每个preSum[i+1]为preSum[i]加上arr[i]的值。

双层循环遍历子数组：

外层循环遍历奇数长度i，从1开始，每次增加2。

内层循环遍历每个起始点j，确保子数组的长度为i，并计算其和。

累加子数组和：

使用前缀和数组快速计算子数组的和preSum[j + i] - preSum[j]，并累加到结果res中。

这种方法通过预先计算前缀和，使得每个子数组的和计算过程变得高效，从而优化了整体的时间复杂度。尽管时间复杂度为O(n²)，但该方法在实际应用中表现良好，尤其是当数组长度适中时。

转载地址：http://ubjs.baihongyu.com/

你可能感兴趣的文章