20200306

Plan

1. LeetCode每日打卡问题 - 20mins

Notes

今天仍然偷了懒，不看书和文档，仅仅选做一道题目。今天的问题是 57 - II. 和为s的连续正数序列。

我的解法

枚举 + 暴力搜索。最外层循环记录最左的index，中间循环记录从index开始，是否可以得到一个合法的正数序列。内部循环中，以一个vector存储中间结果，每次判断之前求和。加上求和的时间复杂度，实际上的时间复杂度为O(n^3)；

有脑子的解法

采用类似滑动窗口的思想。在任意时刻，从left到right的数组，都可以被归纳到以下的情况中：

1. sum(left, right) < target，right++
2. sum(left, right) = target，得到一个合理解，记录，之后left++
3. sum(left, right) > target，left++

另外要单独证明的解的完备性。想要证明这点，最重要的是需要证明right，在left++之后，一定不需要减去1。上面情况中：

1. 1和2明显不不需要左移动right
2. 如果sum(left, right) > target，sum(left, right - 1) < target，则，一定有sum(left+1, right-1) < target，因此，我们可以直接尝试sum(left+1, right)是否符合规则

More

也许我还是该明天起来先总结和归纳一下高中学的数学归纳法。上面的完备性证明是看了半天之后的总结。