返回信息流把一个数组分成四份，三个分割点不算进求和中，使得每份的和要相同。如果可以返回true,如果不能分为四份和一样的就返回false。
{2，5，1，1，1，1，4，3，7，5，7} 比如这数组，分为四份，每份的和相同，分割点不算，分为{2，5} {1，1，1，4}，{7}，{7}.。设计的函数时间复杂度不超过O（n）
发自「贵邮」
这是一条镜像帖。来源：北邮人论坛 / java / #55292同步于 2017/3/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
阿里实习算法题，大神进来看看吧
StarryZJY
2017/3/1镜像同步37 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
太难了。。
我能想到的，前后一个分割点交替向中间靠，若两端相等，则找中间一个分割点另中间两半相等（二分思想），与两端相等就返回
稍微优化一下，找中间分隔点，若中间两段都大于最外两段，则break
复杂度大概是n lgn
帮@nuanyangyang，看她会不会...
你这个复杂度是怎么算的呀，我感觉按照你的思路时间复杂度应该不是nlogn吧
【 在 ml3615556 的大作中提到: 】
: 太难了。。
: 我能想到的，前后一个分割点交替向中间靠，若两端相等，则找中间一个分割点另中间两半相等（二分思想），与两端相等就返回
: 稍微优化一下，找中间分隔点，若中间两段都大于最外两段，则break
: ...................
我自己的思路：
两端向中间靠的指针，复杂度o(n)
每次两端相等，找第三个分割点(2分查找的思路)，复杂度o(lgn)
最差的情况，复杂度o(n lgn)
后面那个思路是实实在在的o(n)，不过有前提是正数组才行
【 在 HB0318 的大作中提到: 】
: 你这个复杂度是怎么算的呀，我感觉按照你的思路时间复杂度应该不是nlogn吧
我感觉找第三个分割点你这两种思路都没法做到复杂度为常数吧。求教了。
【 在 ml3615556 的大作中提到: 】
: 我自己的思路：
: 两端向中间靠的指针，复杂度o(n)
: 每次两端相等，找第三个分割点(2分查找的思路)，复杂度o(lgn)
: ...................
第一个确实没办法做到常数。
第二个思路是：
sum[i] -> 前i个数的和
hashmap<sum, i> -> 和为sum的前i 个数 //这里要求数组全为正，sum严格单调才行，不然会有重复的sum
试着找第一个分割点（o(n)），得到第一个分割点前的和，然后用hash向后找3个分割点(3 o(1))，如果最后一个落在数组尾部，那么找到该分割点。
复杂度o(n)
【 在 HB0318 的大作中提到: 】
: 我感觉找第三个分割点你这两种思路都没法做到复杂度为常数吧。求教了。
next = map.getOrDefault(sums[i] + sums[next + 1], -1)) > 0
请问这段代码怎么理解？
【 在 ml3615556 的大作中提到: 】
: 太难了。。
: 我能想到的，前后一个分割点交替向中间靠，若两端相等，则找中间一个分割点另中间两半相等（二分思想），与两端相等就返回
: 稍微优化一下，找中间分隔点，若中间两段都大于最外两段，则break
: ...................
找下一个分割点的前一位，也就是找下一段的终点。
sum[i] -> 每一段的和
sums[next + 1] ->包含分割点的前几段的和
【 在 zyqbit 的大作中提到: 】
: next = map.getOrDefault(sums[i] + sums[next + 1], -1)) > 0
: 请问这段代码怎么理解？