数组问题总结

参考链接：
https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html#%E4%BA%8C%E5%88%86%E6%B3%95

四种数组解题思想

二分法

考察数组的基本操作，思路很简单，但是通过率在简单题里并不高。

可以使用暴力解法，通过这道题目，如果追求更优的算法，建议试一试用二分法，来解决这道题目

• 暴力解法时间复杂度：O(n)
• 二分法时间复杂度：O(logn)

二分法是算法面试中的常考题。

双指针法

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

• 暴力解法时间复杂度：O(n^2)
• 双指针时间复杂度：O(n)

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。

滑动窗口

• 暴力解法时间复杂度：O(n^2)
• 滑动窗口时间复杂度：O(n)

要理解滑动窗口如何移动 窗口起始位置，达到动态更新窗口大小的，从而得出长度最小的符合条件的长度。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

模拟行为

模拟类的题目在数组中很常见，不涉及到什么算法，就是单纯的模拟，十分考察大家对代码的掌控能力。

总结