题目分析
这个题目和Leetcode76题是类似的,只不过第76题是字符串,而这个题目是数组。当时做那个题目的时候,还没有想记录自己的刷题过程,因此那个题目没有写博客,今天做了这个题目,发现似曾相识,给小伙伴们介绍一下这样的题目应该如何求解。
双指针
这个题目肯定是不能使用暴力法进行求解的,就算是使用DP来解,也要$O(n^2)$的时间复杂度,对于1e5这个量级的数据,我们只能使用$O(nlog(n))$以下的算法进行求解。
双指针是求解这个问题的最优方案,也可以称之为滑动窗口(Sliding Window)。什么意思呢?就是建立左右两个指针,其中左右指针中间的元素称为窗口,因为左右指针在不断右移,因此称为滑动窗口。
我们先找到满足条件的右窗口,然后再收缩左窗口。如果左窗口不满足条件,说明此时左右窗口处恰好满足其中一个解。然后我们继续右移有窗口,到下一次满足条件的位置,然后再次收缩左窗口,直到右窗口到达数组的边界。
在滑动过程中,我们要用哈希表记录small中每一个元素出现的次数。如果次数都大于1,说明满足条件,右窗口停止滑动,开始滑动左窗口,如果次数有一个等于0,那么不满足条件,左窗口停止,开始滑动右窗口。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
刷题总结
滑动窗口是一个非常非常重要的知识点,和单调栈,单调队列类似,都是线性的时间复杂度,是面试笔试中的常客,小伙伴们要多多留心。