I am trying to solve the Leetcode problem '1588. Sum of All Odd Length Subarrays'. 'Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr, where a subarray is a contiguous subsequence of the array'.

我正在试着解决Leetcode问题“1588，所有奇数长子数组之和”。‘给定一个正整数arr数组，返回arr的所有可能的奇数长子数组之和，其中一个子数组是数组的连续子序列’。

My attempt was the following:

我的尝试如下：

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        sub_array_size = 1
        odd_array_sum = 0
        index = 0
        while sub_array_size <= len(arr):
            for element in arr:
                index = arr.index(element)
                if index <= (len(arr) - sub_array_size):
                    for i in range(sub_array_size):
                        odd_array_sum += arr[index + i]
                else:
                    continue
            
            sub_array_size += 2
        
        return odd_array_sum

It has worked for some test cases but failed for most, e.g. arr = [7, 6, 8, 6]. My idea was start with length = 1, increment this by 2 each time we go through the list, then while the index of the element you're on is small enough such that a sub-array of that given odd length can be made, add the elements which would be contained in that sub-array to the sum, and continue this until you find an index too large for this to be possible, then increase the length of the sub-array and start from the beginning of the list again if sub_array_size <= len(arr), otherwise stop as you can't find anymore odd-length subarrays.

它对一些测试用例有效，但对大多数测试用例都失败了，例如ARR=[7，6，8，6]。我的想法是从LENGTH=1开始，每次我们遍历列表时递增2，然后当您所在的元素的索引足够小以至于可以生成给定奇数长度的子数组时，将该子数组中包含的元素加到总和中，并继续这样做，直到您发现索引太大而不可能这样做，然后增加子数组的长度，如果SUB_ARRAY_SIZE<=len(Arr)，则再次从列表的开头开始，否则停止，因为您找不到更多的奇数长度的子数组。

Note that I think I can put 'break' instead of 'continue' to reduce run time as once the index is too large for the given element, all elements after it will have an index too large also so don't need to be checked, but just left it as continue for now as I wasn't 100% sure break wouldn't skip over 'sub_array_size += 2', but I think it wouldn't.

请注意，我认为我可以使用‘Break’而不是‘Continue’来减少运行时间，因为一旦索引对于给定的元素来说太大，它之后的所有元素都会有一个太大的索引，所以不需要检查，但现在只是将其保留为Continue，因为我不100%确定Break不会跳过‘SUB_ARRAY_SIZE+=2’，但我认为它不会。

I can't understand where I've gone wrong and want to figure out where the error is instead of just looking up a solution online.

我不明白我哪里错了，我想找出错误在哪里，而不是只在网上查找解决方案。

The immediate problem is that index = arr.index(element) will not always give you the index of the iterated value. If that value has more than one occurrence, then eventually you will get a lesser index than expected.

直接的问题是index=arr.index(元素)并不总是为您提供迭代值的索引。如果该值不止一次出现，那么最终您得到的索引将比预期的要小。

You can correct this by iterating the index. You can for instance use enumerate and get both the index and value at the same time:

您可以通过迭代索引来纠正这一点。例如，您可以使用ENUMERATE，同时获取索引和值：

            for index, element in enumerate(arr):

This will solve the problem at hand.

这将解决手头的问题。

But this is not a very efficient solution. If it passes the larger tests, it will rank among the slower submissions.

但这并不是一个非常有效的解决方案。如果它通过了更大的测试，它将跻身于提交速度较慢的测试之列。

Instead of iterating all possible list slices (of odd length), try to find for each index, how many odd slices include that index, and then multiply the value at that index with that frequency.

与其迭代所有可能的列表切片(奇数长度)，不如尝试为每个索引查找包含该索引的多少奇数切片，然后将该索引处的值乘以该频率。

Here is a spoiler that implements that idea:

以下是一个实现这一想法的剧透：

def sumOddLengthSubarrays(self, arr: List[int]) -> int:
n = len(arr)
return sum(
( (1 + i // 2) * ((n - i + 1) // 2)
+ ((i + 1) // 2) * ((n - i) // 2) ) * val
for i, val in enumerate(arr)
)