Command Sequence-题解

  这个题有很多做法,我只解释我的做法,首先我们知道U-D,L-R是相互抵消的,然后找这一个序列里面多少个区间是抵消回到原点的

那我们这么想,把U-D看成(1,-1),L-R看成(1e6,-1e6),这样就可以转换成一个一维数组区间和为0的个数,为什么是看成(1e6,-1e6)

是因为题数据n的范围最大是1e5,假如把L-R看成(1e4,-1e4),那么1e4个U会和R抵消那么就出问题了。

然后找区间和为0的个数我们会想到有前缀和优化,但是这个题数据量是1e5很大,你用前缀和优化写两重循环或者优化成n根号n都是不行的,

我的思路是当一个数出现时记录他出现的次数,如果为0就记为1,否则ans(区间和为0的个数)就+1,原因很简单,比如(1,3)的区间和

为2的时候,然后(1,5)的区间和也为2,那么说明(4,5)区间和为0,所以可以实现O(n)复杂度。

上一篇:快速排序。


下一篇:Mybatis1