[LeetCode]Three Equal Parts

这道题brute force的做法就是枚举所有可能，时间复杂度O(n^3)，显然是过不了test case的。考虑这道题的数据规模，O(N^2)的解法基本上也过不了。竞赛的时候并没有想出严格意义上O(N)的解法，只是做了一些优化，最后也是将将过了test case。具体的做法是，我们用right[i]表示从i开始到末尾binary所表示的数，注意这里array的长度肯定很长所以我们用真正的数mod 1000000007的结果来表示。我们从左向右扫的时候，一直维护一个所有prefix所表示的数mod之后的值和其对应结尾的坐标，这样当我们每次只需要在prefix中找到值和right[i + 1]是否存在一样的，假设prefix结尾坐标为j，然后check[j + 1, i]表示的是否和right[i + 1]的值一样即可。这个方法虽然worst case仍然是O(n^2)，但是避免了很多不必要的计算，一定程度上优化了performance，这个方法最后也是擦着边过了test case，说明我们还是需要继续优化：


check solution之后，一个显而易见的结论是，三个part的1的数量必须一样。所以我们统计总数k在找到每个1的数量为k / 3的区间，注意我们不允许leading和trailing zeros。之后我们比较这三个区间表示的binary是不是一样的，因为不包含leading和trailing zeros，所以我们直接比较即可。最后需要注意最后一个part的trailing zero，因为这个是无论如何在构建第三个part的时候都没法避免的，之后我们要确保第一个和第二个part之后有大于等于part3的trailing zero的话，那么part1和part2也必定可以表示成part3的样子。时间复杂度O(N)，代码如下: