給定一個非空的正整數列表 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
直接進行暴力破解，需要3層循環，時間復雜度為O(n^3)
第一層循環，遍歷出所有符合條件的子列表長度 small_arr_len
第二層循環，遍歷出原列表的所有元素 arr[i]
第三層循環，對當前找到的奇數子列表，即 arr[i:i+small_arr_len] 中的所有元素進行求和
代碼實現1
def sumOddLengthSubarrays(arr):
res_sum, arr_len = 0, len(arr)
for small_arr_len in range(1, arr_len + 1, 2): # 遍歷所有可能符合條件的子列表長度
for i in range(arr_len): # 遍歷原列表的所有元素
if i + small_arr_len <= arr_len: # 判斷是否越界
for j in range(i, i + small_arr_len): # 對當前奇數子列表求和
res_sum += arr[j]
return res_sum
上面的方法中，可以看到第三層循環時，每次都需要對 i 到 i + small_arr_len - 1 下標的元素進行重復的求和計算，如果我們能找到一種方法，實現快速計算出兩個下標之間的所有元素的和，那麼就可以對上面方法實現優化。
在這裡，我們可以利用 前綴和 來實現，比如針對列表 arr = [1, 4, 2, 5, 3]，我們可以得到從第一個位置到當前位置的所有元素之和，也就是一個前綴和的列表 pre_sum_list = [1, 5, 7, 12, 15]，當我們需要計算下標 2 到下標4 的子列表 [2, 5, 3] 所有元素之和，就可以直接通過計算 pre_sum_list[4] - pre_sum_list[2 - 1] = 15 - 5，得到結果 10
使用前綴和列表，時間復雜度為O(n^2)
最開始先使用一個循環，計算並得到一個包含有前綴和的列表 pre_sum_list
接著再計算所有奇數長度子列表的和，第一層循環，遍歷出所有符合條件的子列表長度 small_arr_len
第二層循環，遍歷出原列表的所有元素，下表為 i
第三層循環，對當前找到的奇數子列表 arr[i:i+small_arr_len] ，借助 pre_sum_list 求出所有元素之和，如果當前位置為 0 ，那麼當前奇數子列表之和為 pre_sum_list[i + small_arr_len - 1]，否則為 pre_sum_list[i + small_arr_len - 1] - pre_sum_list[i - 1]
代碼實現2
''' 學習中遇到問題沒人解答？小編創建了一個Python學習交流群：711312441 尋找有志同道合的小伙伴，互幫互助,群裡還有不錯的視頻學習教程和PDF電子書！ '''
def sumOddLengthSubarrays(arr):
res_sum, arr_len = 0, len(arr)
pre_sum_list = [0] * arr_len
for i in range(arr_len): # 獲取前綴和列表
pre_sum_list[i] = pre_sum_list[i - 1] + arr[i] if i != 0 else arr[i]
for small_arr_len in range(1, arr_len + 1, 2): # 遍歷所有可能符合的子列表長度
for i in range(arr_len): # 遍歷原列表
if i + small_arr_len <= arr_len: # 判斷是否越界
if i == 0:
res_sum += pre_sum_list[i + small_arr_len - 1]
else:
res_sum += pre_sum_list[i + small_arr_len - 1] - pre_sum_list[i - 1]
return res_sum
上面方法的時間復雜度為O(n^2)，那麼有沒有更優的解決辦法呢？
我們可以直接利用 數學方式 來求和，本題目的是為了計算出所有奇數長度子列表的和，換個角度思考下，我們只需要求出原列表中每個元素在所有奇數長度子列表中出現的次數即可，這樣一來，我們再對每個元素按其出現次數求和，最後再相加就能得到最終結果了。
針對列表 arr = [1, 4, 2, 5, 3] 中的元素 4，其左側元素個數為 1 ，右側元素個數為 3，包含元素 4 的所有奇數長度子列表分為以下兩種情況：
第一種情況，因為 奇數個 + 1 + 奇數個 = 奇數個，所以可從元素4 左右兩側均取奇數個，從左側取奇數個的方法有 1 種（取1個），從右側取奇數個的方法有 2 種（取1個、取3個），組合起來總的方法就有 1 * 2 = 2種：[1, 4, 2]、[1, 4, 2, 5, 3]
第二種情況，因為 偶數個 + 1 + 偶數個 = 奇數個，所以可從元素4 左右兩側均取偶數個，從左側取偶數個的方法有 1 種（取 0 個），從右側取奇數個的方法有 2 種（取0個、取2個），組合起來總的方法就有 1 * 2 = 2種：[4]、[4, 2, 5]
接著把上面兩種情況相加 2 + 2 = 4，該結果表示所有奇數長度子列表中，包含有元素4的情況一共有4種，也就是說元素4在 所有奇數長度子列表 中的出現次數為4，所以此時可以求出所有奇數長度子列表中的元素4之和：4 * 4 = 16
最後，分別求出每個元素在 所有奇數長度子列表 中的出現次數並依次求和，就可以得到最終結果。
使用數學方式求和，只需循環一次，時間復雜度為O(n)
遍歷過程中，首選分別求出當前元素左側及右側的元素個數 count_left,、count_right
從當前元素左右側只取奇數個元素，分別求出從當前元素左側及右側取奇數個元素的可能性left_odd、right_odd
從當前元素左右側只取偶數個元素，分別求出從當前元素左側及右側取偶數個元素的可能性 left_even、right_even
接著分別求出取奇數個和偶數個的所有組合的可能性 odd_all、even_all
最後得到當前元素在 所有奇數長度子列表 中的出現次數為 odd_all + even_all ，並可對當前元素進行最終求和
代碼實現3
def sumOddLengthSubarrays(arr):
res_sum, arr_len = 0, len(arr)
for i in range(arr_len):
# count_left 表示當前元素左側的元素個數，count_left 表示當前元素右側的元素個數
count_left, count_right = i, arr_len - i - 1
# 奇數 + 1 + 奇數 = 奇數, left_odd 表示從當前元素左側取奇數個元素, right_odd 表示從當前元素右側取奇數個元素
left_odd, right_odd = (count_left + 1) // 2, (count_right + 1) // 2
# 偶數 + 1 + 偶數 = 奇數, left_even 表示從當前元素左側取偶數個元素, right_even 表示從當前元素右側取偶數個元素
left_even, right_even = count_left // 2 + 1, count_right // 2 + 1
# odd_all 表示從兩側均取奇數個元素的所有可能性, even_all 表示從兩側均取偶數個元素的所有可能性
odd_all, even_all = left_odd * right_odd, left_even * right_even
# 所有子列表中統計出當前元素的個數 odd_all + even_all ，對當前元素求和即可
res_sum += arr[i] * (odd_all + even_all)
return res_sum
