《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]累加到答案中即可。
可以不记录cnt[]