【LeetCode】所有奇数长度子数组的和 Java 题解

关注

发布于: 4 小时前

题目描述

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组定义为原数组中的一个连续子序列。

请你返回 arr 中所有奇数长度子数组的和。

示例 1：
输入：arr = [1,4,2,5,3]输出：58解释：所有奇数长度子数组和它们的和为：[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我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题是奇数长度连续子序列求和问题。奇数这个概念就不解释了，代码表示就是 i += 2。连续的子数组容易理解。
首先，我们可以根据题意写出朴素代码，代码如下。朴素解法通过之后，发现在整体代码运行计算中，有很多重复计算。
在数组元素求和计算中，一般使用前缀和的思想优化，减少重复计算。前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前 n 项的和”。前缀和优化的代码如下。

通过代码

朴素解法

    public int sumOddLengthSubarrays(int[] arr) {        int ans = 0;        int n = arr.length;        for (int start = 0; start < n; start++) {            for (int length = 1; start + length <= n; length += 2) {                int end = start + length - 1;                for (int i = start; i <= end; i++) {                    ans += arr[i];                }            }        }        return ans;    }

复制代码

前缀和优化解法

    public int sumOddLengthSubarrays(int[] arr) {        int ans = 0;        int n = arr.length;        int[] prefixSums = new int[n + 1];        for (int i = 0; i < n; i++) {            prefixSums[i + 1] = prefixSums[i] + arr[i];        }
        for (int start = 0; start < n; start++) {            for (int length = 1; start + length <= n; length += 2) {                int end = start + length - 1;                ans += prefixSums[end + 1] - prefixSums[start];            }        }        return ans;    }

复制代码

总结

朴素解法的时间复杂度是 O(n * n * n), 空间复杂度是 O(1)
前缀和优化解法的时间复杂度是 O(n * n), 空间复杂度是 O(n)
坚持算法每日一题，加油！

发布于: 4 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/741e9a85cf967d944e685fc63】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】所有奇数长度子数组的和 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论