数组

基础

  1. 数组是存放在连续内存空间上的相同数据类型的集合
  2. 数组的下标都是从0开始的，内存空间的地址是连续的。

  3. 时间复杂度：

    1. 访问：O(1)
    2. 查找：O(n)
    3. 插入： 平均O(n)，最好的情况下O(1)，也就是在数组尾部插入O(1)，最坏的情况下O(n)
    4. 删除：平均O(n)，最好的情况下O(1)，也就是在数组尾部删除O(1)，最坏的情况下O(n)

      经典题目

  4. 二分法：要求是升序数组。先定义好初始区间，当中值小于目标值时，转移到右半区间查找，反之转移到左半区间查找。找到的话就返回mid值，找不到的话就返回-1。有左闭右闭和左闭右开两种写法，注意区分。要能够手撕二分法。

  5. 双指针法（快慢指针）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。在数组和链表中都很常见。是很重要的思想，需要掌握。
  6. 滑动窗口：有点像双指针，不过是滑动窗口指的是两个指针之间的内容，通过移动窗口起始位置来动态更新窗口大小，从而找到符合条件的最小长度。是很精妙的方法，需要多练。

链表

基础

  1. 链表的种类主要为：单链表，双链表，循环链表
  2. 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
  3. 复杂度
    1. 头部插入：O(1)
    2. 尾部插入：如果已知尾节点O(1)，否则需要遍历到尾节点，然后加入新节点O(n)
    3. 插入：插入到已知节点的后面O(1)，需要先查找后插入O(n)
    4. 查找：O(n)
    5. 删除：删除已知节点O(1)，需要先查找后删除O(n)

  4. 虚拟头结点是很重要很方便的方式，因为可以不用单独判断和处理头结点。

    经典题目

  5. 反转链表：原地翻转链表需要搞清楚三个节点之间指向的关系，如果顺序写错了就会导致断链。

  6. 删除链表的倒数第N个节点：快慢指针的经典应用，让快指针先走N步，然后快慢指针同时移动，让快指针到链表尾的时候，慢指针指向的节点就是需要删除的节点。
  7. 环形链表：快慢指针的另一个经典应用。通过步伐不一样的快慢指针来确定是不是有环，快指针每次走两步，慢指针每次走一步，如果链表有环，那么两者一定会在环内相遇。慢指针记住此时的相遇点，让快指针回到头结点开始，两者此时每次都走一步，当两者再次相遇的时候，就是环的入口。