CTF of Z2BNS
0%

所有奇数长度子数组的和

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 735 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

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

示例1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：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

示例2：

1
2
3
输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

示例3：

1
2
输入：arr = [10,11,12]
输出：66

提示：

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

多个for循环遍历，遍历所有可能的奇数子数组的长度i，然后再遍历所有长度为i的子数组个数，遍历每一个长度为i的子数组求和。

我这个思路是直观解法，应该挺麻烦的，可能有更好的答案，等看题解吧

c++代码：(执行用时12ms，击败37.26%，内存消耗8.5M，击败20.68%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int result=0;
        //遍历所有的奇数子数组，i为子数组的长度
        for(int i=1;i<=arr.size();i+=2){
            //遍历arr数组,j为长度为i的子数组的个数
            for(int j=0;j<arr.size()-i+1;++j){
                //计算长度为i的每个奇数子数组的和
                for(int k=0;k<i;++k){
                    result+=arr[k+j];
                }
            }
        }
        return result;
    }
};

解法二：还有一种效率更高的解法就是计算每个元素在奇数长度子数组中出现的次数，通过看题解得到思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
* odd奇数，even偶数
* 对于每个元素i(数组中下标为i)来说，要构成奇数长度的子数组
  即 i左边的元素个数left+i本身自己一个+右边元素的个数right=奇数
  即 left+right=偶数
* 满足a+b=偶数就只有两种情况
  1. 奇数+奇数=偶数
  2. 偶数+偶数=偶数
* 1. 所以只需要求得i左边可以选择奇数长度的可能有多少种，即left_odd,同样求右边奇数right_odd
     就可以求出策略1有多少种可能
  2. 所以只需要求得i左边可以选择偶数长度的可能有多少种，即left_odd,同样求右边偶数right_odd
     就可以求出策略1有多少种可能，注意0也算选择的一种可能
* 即元素i在所有奇数长度子数组出现的次数总和是
  left_odd*right_odd+left_even*right_even
* 元素i左边元素共有i个，右边元素共有siz-i-1个

c++代码：（执行4ms，击败91.05,%，内存8.6M，击败8.85%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {

        int res = 0;
        for(int i = 0; i < arr.size(); i ++){
            int left = i + 1, right = arr.size() - i,
                left_even = (left + 1) / 2, right_even = (right + 1) / 2,
                left_odd = left / 2, right_odd = right / 2;
            res += (left_even * right_even + left_odd * right_odd) * arr[i];
        }
        return res;
    }
};
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

没有官方题解，我提交的代码时间复杂度是$O(n^3)$，然后看别人的题解有复杂度$O(n)$的方法，其实就是计算每个元素在奇数长度子数组中出现的次数，做的时候我考虑过，因为时间问题就选择了这个暴力解法，毕竟也能通过不是吗😏，现在还是刷题没考虑太多最优解的问题，不然真的要花费很多时间，现在事情多也不能专门去研究这种题。

------------- THE END! THANKS! -------------