子数组相关

相关题目

• 209. 长度最小的子数组

• 53. 最大子数组和

对应解答及注意事项

长度最小的子数组

• 这个题是滑动窗口的最佳实践！窗口有左右两个边界索引，有点类似于双指针的方法
• 官方题解有一个前缀和的做法：提前算出[0, i]的和，并保存到一个额外的数组中，接着将题目转化为：找到两个前缀和，[0, i)，[0, j)使得这两个前缀和的差 >= target，记录此时的子数组长度为：j-i+1。后续的操作全都转化为了对前缀和数组的查询操作。

最大子数组和

• 这题可以用动态规划的方法
• 评论区有提到前缀和数组的方法：也是提前算出前缀和，子数组的和可以转化为两个前缀和的差。对于前缀和数组来说，题目转化为了股票购买/卖出最佳时机（可以多次持有股票，但手上最多只能有一支股票）