这只是一只菜鸡开始刷leetcode的心路历程以及记录，我会把学习过程中的思路和想法记录下来，也会用可视化的方法把方法尽可能画出来（花里胡哨的笔记x），希望能成为一名高冷、无情的做题机器（bushi）。
遇到一些关于数组、相邻子数组的问题时，可以运用 滑动窗口 的方法进行解决，滑动窗口的好处暂时我认为是能够保存具有某段长度的历史信息，省去冗余重复的计算。按照课程的Intro，就从找到数组中子数组的平均值 为例子好了。
怎么看也是大一计算概论中比较简单的入门题（x ，一般来讲，比较无脑的做法是给定子数组长度 K，我们做两重循环，外层循环控制最后的输出长度，内层循环控制最后的输出内容，在内层循环每次把元素加起来除以K就可以得到最后答案$Output_{i}$。这样的做法好处只有一个，就是直观易懂哈哈。但是其时间复杂度是比较不行的，假设输入数组长度为 N，子数组长度为K，那么算法的时间复杂度就是$O(N*K)$。
这样可不行，面试官肯定问你要怎么优化的，那咋整啊。这时候我们的主角 滑动窗口 ，还不能出场。我们先看Intuition，我们刚才的方法十分糟糕，我们叫它SuperBad方法好了，简称
重复计算、冗余，这些都是面试官会找你麻烦的东西。——吟游码农迪克
而且我们发现，计算两次平均值的时候，差异就在于最前面的元素被剔除了，最后的元素被加进来了，这时候主角就可以登场了，滑动窗口每次向右平移一格，自然就是我们前面所说的模式了。这样的话，我们只需要维护第一个元素和最后一个元素就好了，可以用队列实现，但是课程中的代码是比较朴素的实现方法，并不涉及数据结构，这样的方法能够在$O(N)$的时间内进行。
代码在这里
#brute force
def find_average_of_subarray(K,arr):
result = []
for i in range(len(arr) - K + 1):
_sum = 0.0
for j in range(i,i+K):
_sum += arr[j]
result.append(_sum/K)
return result
#sliding window
def find_avg_slidingVer(K,arr):
result = []
_sum = 0.0
front = 0
for i in range(len(arr)):
_sum += arr[i]
if i >= K - 1:
result.append(_sum/K)
_sum -= arr[front]
front += 1
return result
def main():
K = 5
result = find_average_of_subarray(K,[1,3,2,6,-1,4,1,8,2])
result_2 = find_avg_slidingVer(K,[1,3,2,6,-1,4,1,8,2])
print(f"Average of subarray of size {K}: " + str(result))
print(f"Average of subarray of size {K}: " + str(result_2))
main()