找到一个数组的【所有奇数个数的】子数组

左手的ㄟ右手 2022-12-20 12:53 100阅读 0赞

#### 解法 ####

#### 问题2：有一个数组A(长度为n)，求出数组 A中包含第i个元素`A[i]`的子数组的个数？ ####

1, 在子数组中，以A\[i\]为起点的数组，有`n - i` 个

2，不以`A[i]`为起点的数组，前半部分一共有 `i`中情况，后半部分有`n-i`种情况，那么不以`A[i]`为起点一共有 `( n - i ) * i` 个

所以包含`A[i]`的所有子数组一共有 `( n - i ) + (n - i) * i` 个

也就是 `( i + 1 ) * ( n - i )`个

--------------------

#### 根据上述结论 ####

##### 1, 所以包含A\[i\]的奇数个数的数组总和为 #####

`((i + 1) * (n - i) + 1) / 2`

##### 2, 所以包含A\[i\]的偶数个数的数组总和为 #####

`((i + 1) * (n - i) ) / 2`

有小数的情况 向下取整。

--------------------

#### 为什么记录这个： ####

[1588. Sum of All Odd Length Subarrays  
][1588. Sum of All Odd Length Subarrays]

#### 解析 ####

[https://web.stanford.edu/class/cs9/sample\_probs/SubarraySums.pdf][https_web.stanford.edu_class_cs9_sample_probs_SubarraySums.pdf]

[https://leetcode.com/problems/sum-of-all-odd-length-subarrays/discuss/854184/JavaC%2B%2BPython-O(N)-Time-O(1)-Space][https_web.stanford.edu_class_cs9_sample_probs_SubarraySums.pdf]

[1588. Sum of All Odd Length Subarrays]: https://leetcode.com/problems/sum-of-all-odd-length-subarrays/
[https_web.stanford.edu_class_cs9_sample_probs_SubarraySums.pdf]: https://web.stanford.edu/class/cs9/sample_probs/SubarraySums.pdf