美团3.9笔试

#美团##春招#
签到200
第三题 数组前缀合 100 可以参考力扣304。
第四题 用的前缀和做的，复杂度应该在nlogn，为什么只能通过70%的用例，有兄弟知道吗？ 
经评论区提醒，应该结果是longlong，难受
简单写一下思路，有多少个0，就是看有多少个5和2。我这里把2和5的数量简写为presum了。
如何看删除区间呢？例如，我们对0.....l.....r.....n-1,删除其中的l-r部分，那么剩余2和5的数量应该是
presum[n-1]-presum[r]+presum[l-1];
那么对于以y为结尾的区间，有多少个合法的删除区间呢？
如果presum[n-1]-presum[y]>=k,那么显然，0到y，1到y,.....y-1到y，y都是合法区间。
如果把presum[n-1]-presum[y]<k,那么删除区间就需要缩短。假设存在最小的x，使得presum[n-1]-presum[y]+presum[x]>=k,那么x到y，x+1到y.....y-1到y，都是合法区间，也就是需要找到合适的x。
由于presum数组是递增的，因此可以利用二分查找的方式找到x（但是我第一遍用遍历，复杂度On2时间好像也没超）
整体时间复杂度是n(遍历以y结尾的区间)✖️logn(二分查找x的位置)=nlogn。
第五题 不会 10 
经评论区提醒，倒叙作操作，把删边操作转化为增边操作，就可以用并查集解决了。
380够吗，能进面试吗