Sum of All Odd Length Subarrays

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

分析

枚举起点 i 和终点 j，累积和

双重循环遍历 arr，枚举所有可能的子数组起点 i 和终点 j
维护 sum 变量，计算 arr[i] ~ arr[j] 的子数组和：
- 每次 j 递增，就加上 arr[j]
- 如果 j - i + 1 是奇数，说明当前 sum 是一个奇数长度子数组和，就将当前 sum 累加到 res 里

时间复杂度

时间复杂度 O(n^2)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution
{
public:
    int sumOddLengthSubarrays(vector<int>& arr)
    {
        int res = 0;
        for (int i = 0; i < arr.size(); ++i)  // 遍历子数组的起点 i
        {
            int sum = 0;
            for (int j = i; j < arr.size(); ++j) // 遍历子数组的终点 j
            {
                sum += arr[j]; // 计算子数组和
                if ((j - i + 1) % 2 == 1) // 仅当长度为奇数时才累加
                    res += sum;
            }
        }
        return res;
    }
};