关于LC209优化暴力解的思路

Question

波波老师您好，以下是我优化暴力解的思路，不知道是否正确。

我们创建一个新的变量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)

请问老师这样的思路是否正确？

谢谢老师

Answer 1

liuyubobobo 2019-06-04 19:19:43

思路是正确的，但是这个问题使用滑动窗口的思路，可以把复杂度降到O(n)级别：）

这是因为，我们如果已经知道了0， 1， 2， 3， 4 五个元素的和，直接减去第0个元素，得到的就是1，2，3，4四个元素的和：）

我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0209-Minimum-Size-Subarray-Sum/cpp-0209/main4.cpp

看看能不能理解？：）

继续加油！：）

• 提问者 软件工程小白菜 #1

  非常感谢！刚听了滑动窗口的课，有理解！