[LeetCode] 805. 数组的均值分割

设变量 sum: 数组的和，n:数组元素个数，tot: 子数组和，cnt:子数组元素个数
通过简单的公式变换可以得到：sum / n = tot / cnt
sum / n 的值是确定的，所以也就是需要找到一个子数组的平均值为 sum / n
最简单的方法是通过二进制枚举进行查找，但 n <= 30，可能会超时
如果 n 能够小一半就能够通过枚举进行查找了
我们尝试将数组平均分为左右两半，对每个分数组进行枚举判断
但是会漏掉同时包含两个分数组中元素的子数组
也就是说存在左右分数组中平均值不等于 sum / n，但是合起来等于 sum / n
假设已知左分数组: tot_left, cnt_left，想要在右分数组中找到 tot_right, cnt_right，使得 (tot_left + tot_right) / (cnt_left + cnt_right) = sum / n
这个并不容易操作：因为这里面有两个变量 tot_right 和 cnt_right
如果平均值为0的话，就可以转换为 1 个变量： tot_left + tot_right = 0
所以只要判断右数组中有没有值等于 -tot_left 的就行了
上面通过枚举一半，然后判断另一半中是否有对应答案的方法是折半查找。

原文地址：http://www.cnblogs.com/huihao/p/16888259.html