每日一题系列

文章目录

• 所有奇数长度子数组的和
• 思路一：暴力求解
• • 代码一：暴力求解
• 思路二：数学分析法
• • 代码二：数学分析法
• // 后记

所有奇数长度子数组的和

🏃 给你一个正整数数组 arr
🏃 请你计算所有可能的奇数长度子数组的和。
🏃 子数组定义为原数组中的一个连续子序列。

💘 例如：

🏃 输入：arr = [1,2,3,4,5]
🏃 输出：57

💘 解释：

🏃 子序列长度为 1 的有：[1] [2] [3 ][4] [5]，和为 1+2+3+4+5=15
🏃 子序列长度为 3 的有：[1,2,3] [2,3,4] [3,4,5] 和为 1+2+3+2+3+4+3+4+5=27
🏃 子序列长度为 5 的有：[1,2,3,4,5] 和为 1+2+3+4+5=15
🏃 总计 15+24+15=57

思路一：暴力求解

🏃 依次找出长度为1 3 5 7…的所有组合
🏃 并将他们全部加在一起

🏃 创建三个变量 odd i sumSize
🏃 odd 用来控制子数组的长度
🏃 i 用来控制当子数组长度为 odd 时，需要遍历到数组的哪个位置
🏃 例如，当 arrSize 为 5，odd 为 3 时，只需遍历到下标为 2 的元素即可
🏃 sumSize 用来控制遍历时需要加和的个数

代码一：暴力求解

int sumOddLengthSubarrays(int* arr, int arrSize){    int sum = 0;    int odd=0,i=0,sumSize=0;    //odd用来控制子数组的长度    for(odd=1;odd<=arrSize;odd+=2)    {    //i用来控制当子数组长度为odd时，需要遍历到数组的哪个位置    //例如，当arrSize为5，odd为3时，只需遍历到下标为2的元素即可 for(i=0;i<=arrSize-odd;i++) { //遍历到第i个元素时，向后加sumSize个长度的数     for(sumSize=0;sumSize<odd;sumSize++)     {  sum=sum+arr[i+sumSize];     } }    }    return sum;}

🏃 这种方法属于暴力求解，时间开销为0（n^3），当数组过大时，会造成时间开销过大

思路二：数学分析法

🏃 如果我们能通过分析找出数组中每一个元素在其所有奇数的子序列中出现的次数
🏃 然后将每个数据元素 * 次数然后累加，就可得出结果

💘 下面给出分析思路的过程

🏃 由上图可知，设待检查的元素下标为 i
🏃 左边能选出 i +1 种可能
🏃 其中选出偶数个的可能为（i + 1）/ 2，奇数个的可能为 i / 2
🏃 右边能选出 n - i 种可能
🏃 其中选出偶数个的可能为（n - i + 1）/ 2，奇数个的可能为 （n - i） / 2
🏃 只要能确定个数，左偶数 x 右偶数 + 左奇数 x 右奇数就是下标为 i 的元素一共出现的次数

代码二：数学分析法

//数学方法求解int sumOddLengthSubarrays(int* arr, int arrSize){    //左右可能出现的选择数    int leftOption = 0;    int rightOption = 0;    //左右奇偶选项各会出现的次数    int leftEven = 0, leftOdd = 0;    int rightEven = 0, rightOdd = 0;    int sum = 0;    int i = 0;    for (i = 0; i < arrSize; i++)    { leftOption = i + 1; rightOption = arrSize - i; //左右选出偶数个数的情况 leftEven = (leftOption + 1) / 2; rightEven = (rightOption + 1) / 2; //左右选出奇数个数的情况 leftOdd = leftOption / 2; rightOdd = rightOption / 2; sum = sum + arr[i] * (leftEven * rightEven + leftOdd * rightOdd);    }    return sum;}

// 后记

🏃以后每天更新一道算法题，并且附带超级详细的讲解和注释，所有代码均可复制到编译器里自测。
🏃如果有疑问的小伙伴，欢迎评论留言，我会详细解答。

// 文章中任何错误都请大佬指正。

全民K歌