所有奇数长度子数组的和

难度:

标签:

题目描述

代码结果

运行时间: 20 ms, 内存: 16.0 MB

// 思路：
// 使用 Java Stream API 计算奇数长度子数组的和。利用 IntStream 和 nested for loop 来生成和过滤子数组。

import java.util.stream.IntStream;

public class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        return IntStream.range(0, n)
                .flatMap(i -> IntStream.range(i, n)
                        .filter(j -> (j - i + 1) % 2 != 0)
                        .map(j -> IntStream.rangeClosed(i, j).map(k -> arr[k]).sum()))
                .sum();
    }
}

解释

方法:

该题解采用前缀和和滑动窗口的思路。首先，计算原数组的前缀和数组left_sum，使得left_sum[i]表示原数组arr中前i个元素的和。然后，对于原数组中的每个元素arr[i]，通过滑动窗口的方式计算以arr[i]为起始元素的所有奇数长度子数组的和，并累加到最终结果final中。具体而言，对于每个起始元素arr[i]，窗口长度now_len从1开始，每次增加2，直到窗口超出数组边界。在每个窗口内，计算子数组的和now_sum为left_sum[i + now_len] - left_sum[i]，然后将now_sum累加到final中。

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆

在题解中，为什么选择使用前缀和而不是直接在数组上进行迭代计算每个奇数长度子数组的和？

▷

使用前缀和的主要优势是其能极大地优化求连续子数组和的操作。如果直接在数组上迭代求每个奇数长度子数组的和，每次计算都需要线性时间遍历子数组，导致整体时间复杂度较高。而通过前缀和数组，我们可以在常数时间内得到任何子数组的和，从而显著减少了重复计算，提高了算法效率。

🦆

题解中提到的滑动窗口方法与常见的滑动窗口处理连续子数组问题的方式有何不同？

▷

常见的滑动窗口方法通常用于处理固定长度或最大长度限制的连续子数组问题，窗口大小一般会动态调整但通常是连续滑动。在本题中，滑动窗口的长度始终为奇数，且每次增长步长为2，这是为了专门计算奇数长度的子数组之和。这种使用滑动窗口的方式更加专注于控制子数组的长度，而不仅仅是位置调整。

🦆

计算过程中，为什么窗口长度now_len初始值为1，并且每次只增加2，而不是逐个或其他间隔增长？

▷

题目要求计算所有奇数长度子数组的和。因此，窗口长度now_len从1开始，即最短的奇数长度，并且每次增加2来保持窗口长度始终为奇数。如果窗口长度按1或其他非2的间隔增长，那么我们将无法保证窗口长度始终为奇数，从而无法满足题目的要求。

🦆

在实际编程中，如何保证在计算子数组和时不会出现数组越界的错误？

▷

在编程实现时，需要小心处理边界条件。通过确保在计算子数组和时使用的索引不超出数组范围，可以避免越界错误。在题解中，通过条件`i + now_len <= len(arr)`来保证。这个条件确保即使在最大的窗口长度下，子数组的结束索引也不会超过数组的实际长度。

所有奇数长度子数组的和

题目描述

代码结果

解释

代码细节讲解

相关问题