数组

1、二分搜索法

1、注意：只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法

2、还有：同时题目还强调数组中无重复元素

2、双指针

1、数组的快慢指针，主要就是快指针赋给慢指针，然后最终返回慢指针15

2、这是主要思路

3、参考27题、26题

3、滑动窗口

1、本质上也就是一个双指针

2、一般用来解决长度最小的子数

3、注意循环不变量，这个也很重要

4、一般用来解决字符串啊、数组之类的问题

1、应用场景

1、一般是用来满足关键字：满足xxx条件（计算结果、出现的次数、同时包含）

2、最长、最短

3、子串、子数组、子序列

2、例如：长度最小的子数组

2、滑动窗口使用思路（寻找最长）

1、核心：左右双指针（left，right）、在起始点、right逐位向右滑动循环

2、每次滑动中

3、如果窗口内元素满足，right就会右移，取得最优结果

4、如果窗口内元素不满足，left就会右移，缩小窗口

5、right达到结尾

3、模板

1、思路

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。

4、树状数组

1、理解

1、理解图

2、如果要求计算很多个，就需要用树状数组

2、lowbit概念

1、lowbit (x)是x的二进制表达式中最低位的1所对应的值

2、例如100010：lowbit==2

3、例题307

1、前提

1、求出这个数组所对应的树状数组，就可以用这个写出add的方法

2、b[i+lowbit(i)]就是b[i]正上方的序列

3、如图