C语言重构【1588】所有奇数长度子数组的和

素颜马尾好姑娘i 2022-10-28 14:20 170阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一个正整数数组 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
    示例 2：
    
    输入：arr = [1,2]
    输出：3
    解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
    示例 3：
    
    输入：arr = [10,11,12]
    输出：66
     
    
    提示：
    1 <= arr.length <= 100
    1 <= arr[i] <= 1000

#### 方案： ####

*  注意这里子数组的定义，他是要求连续的，即\[1,4,2,5,3\]的长度为3的子数组为：142，425，253
 *  搞清楚这点就按照题目表述表达算法求和即可

class Solution
    { 
    public:
        int sumOddLengthSubarrays(vector<int> &arr)
        { 
            int len = arr.size();
            int l = 1;
            int res = 0;
            while (l <= len)
            { 
                int sum = 0;
                for (int i = 0; i < l; i++)
                { 
                    sum += arr[i];
                }
                res += sum;
                for (int i = 1; i <= len - l; i++)
                { 
                    sum = sum - arr[i - 1] + arr[i + l - 1];
                    res += sum;
                }
                l += 2;
            }
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n^2)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode