关于LC209优化暴力解的思路
来源：3-7 滑动窗口 Minimum Size Subarray Sum
软件工程小白菜
2019-06-04
波波老师您好，以下是我优化暴力解的思路，不知道是否正确。
我们创建一个新的变量int sum=0，每次遍历以i开头的所有子数组时，都把遍历到的当前元素加给sum。例如在数组{1,2,3,4,5}中，我们遍历以1开头的子数组时，每遍历到一个新的元素，就把这个元素加到sum身上。sum值的变化就为0, 1, 3, 6, 10, 15。当遍历以2开头的子数组时，只需把sum值设为0，然后重复即可。
这样通过另开辟空间记录当前的sum，我们就省去了从头计算子数组和的时间(1, 1+2, 1+2+3等等)，从而使时间复杂度变为O(n^2)
请问老师这样的思路是否正确？
谢谢老师
写回答
1回答
-
思路是正确的，但是这个问题使用滑动窗口的思路，可以把复杂度降到O(n)级别：）
这是因为，我们如果已经知道了0， 1， 2， 3， 4 五个元素的和，直接减去第0个元素，得到的就是1，2，3，4四个元素的和：）
看看能不能理解？：）
继续加油！：）
112019-06-04
相似问题
最长上升子序列暴力解法的复杂度
回答 1
力扣216题的问题
回答 1