《Array Partition》题目分析

比较容易想到的解法是： 1)枚举前后两个断点p和q 2)利用前缀和，快速计算出sum[1..p-1], sum[p..q-1], sum[q..n]三段的和
3)判断以上三个和是否满足相差不超过1的条件，若满足则答案累加1

遗憾的是这个算法时间复杂度是O(N^2)会超时。

一种优化方法是用空间换时间。

我们只枚举q，在q确定的情况下，最后一段的和s[q..n]也是确定的。

同时我们用一个哈希表(hashmap)cnt[], cnt[x]记录sum[1..1], sum[1..2], sum[1..3], ... sum[1..q-2] 中有几个值是x。(cnt[x]也就是有几个p可以使第一段和为x)

初始时，q = 3, cnt[]中只有cnt[s[1..1]]=1, 其余都是0。

当q增加1的时候，cnt[]的变化只需要cnt[s[1..q-2]]++即可。

由于q确定的情况下，最后一段的和s[q..n]也是确定的。所以第一段的和只可能有3种情况，s[q..n]-1, s[q..n], s[q..n]+1。

我们依次枚举第一段的和的情况，不妨设为S1。当第一段的和也确定时，第二段的和也随之确定(总和减去第一、第三段的和)，这是我们可以判断这三个是否满足相差不超过1的条件。

如果满足条件，那么cnt[S1]就是在当前q确定、第一段和是S1时，分3段的答案数。我们把cnt[S1]累加到答案中即可。