复杂度理论

四个复杂度

1. 时间复杂度 - 核心考察点
2. 空间复杂度 - 次要考察点
3. 编程复杂度 - 能看得懂
4. 思维复杂度 - 能想得出

双指针线性复杂度

但有的时候，很明显的小数据的情况下，可以略微损失一点时间复杂度来降低编程复杂度，提高可读性

时间复杂度

P问题 Polynomial

（多项式问题）

• On，On2，On3
• O1，On0.5
• Ologn，Onlogn

NP问题

• O2n，On^n, On!

只考虑最高项

不考虑常数项和系数项

Omax(n, m) = O(n+m)

根据时间复杂度来倒推算法

On算法有

1. 双指针算法：最常见，远大于后面的所有算法的和
2. 打擂台算法：找最大值（一开始赋值成负无穷，每次把最大的打下来）
3. 单调栈算法，四五道题稍微多一些
4. 单调队列算法

双指针

1. 相向双指针（eg判断回文串）

   1. Reverse型

      翻转字符串

      判断回文串

   2. Two Sum型

      两数之和

      1. Hashmap: On, On
      2. 排序+双指针: Onlogn, O1

      三数之和

   3. Partition型

      快速排序

      颜色排序

2. 同向双指针

3. 背向双指针

   非常少见，就几个题

   最长回文串

如果while或if里面过长，则可以考虑可以拆出来一个函数来处理，过长的时候不容易读懂，然后可能出错

返回多个值，需要构建类

两数之和，有十种变形

follow up

1. 排好序的情况下，哪种更好

   双指针

2. 需要返回下标的时候，哪种更好

   hashmap更好

   否则双指针需要将数组转换成一个pair的数组进行排序，保存数值和原来的位置