Array 1588 所有奇数长度子数组的和

2020-10-18

思路：

极端情况：数组只有一个

方法一：暴力破解

双层循环，从第一个元素开始，计算每个元素所在的长度为奇数的数组的和。内层循环将路径上的元素都进行加和，判断是否为奇数数组。

外层循环 i 遍历整数组，以每个 a[i] 为起点的数组
内层 j 循环（初始化为 i）
- 计算路径上的元素和 sum，每次循环都需要重新初始化为 0
- 判断 j-i+1 长度是否为奇数，是就叠加到 ans 中

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int len = arr.length;
        if(len == 1) return arr[0];
    
        // 双层遍历
        int ans = 0;
        for(int i = 0;i < len; i++ ){
            // 每次遍历都需要初始化
            int  sum = 0;
            for(int j = i;j < len ;j++){
                sum += arr[j];
                // 判断是否为 奇数
                if((j-i+1 )%2 == 1) ans+=sum;
            }
        }
        return ans;
    }
}

时间复杂度：双层循环需要 $o(n^2)$

空间复杂度，不需要额外空间。

算法二：

sun = 元素 * 元素在奇数数组中出现的次数（count ）。

找规律，以一个元素为中心点，要想这个元素位于奇数数组中，分为两种情况：

元素的左边有偶数个元素，并且右边也有偶数个元素；
元素的左边有奇数个元素，并且右边也有奇数个元素。
count = 左边元素出现的次数（L） * 右边元素出现的此时（R）。（因为左边元素 + 元素本身、元素本身 + 右边元素、左右元素的组合都是奇数个元素）（这里也可以简单的数据进行类比推到）

假设这个中心元素的下标是(index),那么它的：

左边一共有 left = （index +1）种选择（没有元素，左右0个也算偶数个元素）
- 奇数个有 left /2 中
- 偶数个有(left+ 1)/2 (0 也算)
右边一共有right = （n-index）中选择。
- 奇数个有 right /2 中
- 偶数个有(right + 1)/2 (0 也算)

// 2
// 从第一个元素开始，把每个元素当做模型中的中心元素，
// 计算该元素在奇数数组中出现的次数
int res = 0;
for(int i = 0;i < len; i++ ){
    int left = i + 1,right = len -i;
   int left_odd = left / 2 ,left_even = (left + 1)/2,
   right_odd = right / 2,right_even = (right+1)/2;
   res += arr[i] * (left_even*right_even + left_odd*right_odd);
}
return res;

时间复杂度：一个 for 循环（$O(n)$）

空间复杂度：仅需要常数的额外空间。

总结：每道题找规律，就从简单数据开始。一开始审题不清晰。