数组06--总结
数组06–总结
数组的理论基础
数组是存放在内存连续空间上的相同类型的数据的集合；
两个注意点：
- 下标从
0开始； - 内存地址连续；
So： 正是因为内存地址连续，所以在删除和增加元素的时候，就必须移动其他元素，导致时间开销大！
在C++中，要注意
vector和array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。数组的元素是不能删的，只能覆盖。
数组经典题目
大概四种，对应之前例题
二分法
- 暴力解法：时间复杂度
O(n); - 二分法：时间复杂度
O(logn);
循环不变量原则 : 只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。
双指针法
双指针法（快慢指针法） ： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
- 暴力解法 : 时间复杂度：
O(n^2) - 双指针 : 时间复杂度：
O(n)
数组中的元素为什么不能删除，主要是因为以下两点：
- 数组在内存中是连续的地址空间，不能释放单一元素，如果要释放，就是全释放（程序运行结束，回收内存栈空间）。
- C++中vector和array的区别一定要弄清楚，vector的底层实现是array，封装后使用更友好。
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。
滑动窗口
- 暴力解法 : 时间复杂度：
O(n^2) - 滑动窗口 : 时间复杂度：
O(n)
主要要理解滑动窗口如何移动 窗口起始位置，达到动态更新窗口大小的条件，从而得出长度最小的符合条件的长度。
滑动窗口的精妙之处在于 : 根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。
如果没有接触过这一类的方法，很难想到类似的解题思路，滑动窗口方法还是很巧妙的。
模拟行为
模拟类的题目在数组中很常见，不涉及到什么算法，就是单纯的模拟，考察对代码的掌控能力。
在这道题目中，我们再一次介绍到了循环不变量原则，其实这也是写程序中的重要原则。
相信大家有遇到过这种情况： 感觉题目的边界调节超多，一波接着一波的判断，找边界，拆了东墙补西墙，好不容易运行通过了，代码写的十分冗余，毫无章法，其实真正解决题目的代码都是简洁的，或者有原则性的，大家可以在这道题目中体会到这一点。
总结
