一道面试题

Question

记不太清了，大概是这样，给定一个很大的int数组（题目是是10000），要求把该数组分割成4个子数组（题目中称为切片），子数组的长度没有限制。要求：四个子数组的和相等，存在这样的子数组，输出true。要求算法的时间、空间复杂度都是1，可以使用Java集合最开始想到了回溯法，但是明显不符合要求。

Answer 1

遍历一遍求个和复杂度就已经是N了吧...  不知道这里的复杂度是什么意思.首先  根据你的描述,(或者是我理解错了分割?), 问题是不一定有解的....... 和必须是4的倍数,然后还要能刚好分成这么多块...分块是个很复杂的事情...有一个不是太靠谱的办法,就是排序之后去取头尾的1/2n,然后分成n块...然后再去凑...这是很漫长的过程
 所以 时间复杂度为1好像就是在扯淡一样.. 另外,,,,回溯法去解不一定有解的题目.. 会穷举所有的排列吧.....

Answer 2

http://blog.csdn.net/Molly_1994/article/details/74626468
这个时间复杂度如何达到O(N)还没想到，以后有空再看看

Answer 3

楼主可以看看这篇，解决数组4等分的，之前看过，确实可以实现，并且用空间换取了时间，时间复杂度较低。
http://blog.csdn.net/woaidtt4213/article/details/60506288