题目分析

本题是Leetcode周赛的一个签到题，基本上有一些算法基础的朋友都能做得出来。为什么要把这个题目拿出来分享呢？是希望小伙伴们能够扩展本题的数据量进行计算，当数据量为1e2可以采用哪些方法？数据量为1e3可以采用哪些方法？数据量为1e5可以采用哪些方法？

数学

暴力法这里就不介绍了，三层循环，第一层为子数组长度，第二层位起始数组的坐标，第三层遍历子数组求和。**时间复杂度为$O(n^3)$，空间复杂度为(O(1))**。本题作为简单题也是可以轻松通过的。

这里介绍一种比较容易想到的前缀和优化算法，因为暴力法每次都要对子数组重新求和，可以使用前缀和的方式快速获取子数组的和。此时可以省略最后一层循环，因此**时间复杂度为$O(n^2)$，空间复杂度为(O(n))**，算法很好理解，直接看代码即可。

下面是Java语言的题解

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

优化数学

当我以为这个题目做完的时候，看了一下题解，发现还有更加精妙的解法，下面给小伙伴们介绍。

我们能否计算出来每个元素需要遍历几次呢？

以[1, 4, 2, 5, 3]为例
包含1的子数组有[1], [1, 4, 2], [1, 4, 2, 5, 3]
包含4的子数组有[1, 4, 2], [1, 4, 2, 5, 3], [4], [4, 2, 5]
包含2的子数组有[1, 4, 2], [1, 4, 2, 5, 3], [4, 2, 5], [2], [2, 5, 3]
包含5和包含3的子数组留给你们去填一下吧

可以看出来其中的规律，包含i的数字，起始位置可以从0到i，并且要满足子数组的长度为奇数，说明左右两边的子数组满足同奇偶性。如果左边元素有偶数个，可以有0个，2个，4个到i个，右边的元素可以有0个，2个，4个到(length - i - 1)个，因此左边元素为偶数个满足条件的子数组为((i + 2) / 2) x (length - i + 1) / 2)个。如果左边元素有奇数个同理，满足条件的子数组为((i + 1) / 2) x (length - i) / 2个。可以判断i一共加过多少次，因此只需要遍历i即可。

算法的**时间复杂度为$O(n)$，空间复杂度为(O(1))**。

下面是Java语言的题解

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

刷题总结

这个题目本来是可以想出来的，因为数据量太小，所以没有细想。这也就提醒了我们，在做笔试的时候，我们需要根据数据量选择合适的算法进行解题即可，但是要记得在做完笔试后回去细想能否对算法进行优化。如果面试官考察问到笔试题的时候，能给出更优的方案，那么肯定会获得认可的。