优化技巧
快读快写
C++中，cin的速度慢于scanf，scanf速度慢于getchar，同理，cout速度慢于printf，printf速度慢于putchar
可以利用如下语句将C++中的读入输出速度加快
std::ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);这样可以大幅度提升输入输出速度，当然最快的方法还是手写快读快写。
快读就是把输入的数字按位读取，然后注意判断一下正负号就好。
inline int read() { //快读函数
int s = 0, w = 1; //s是数字数值，w是数字符号
char ch = getchar();
while (ch < '0' || ch>'9') { //判断是不是负号
if (ch == '-') w *= -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
//s=s*10+ch-'0';
s = (s << 1) + (s << 3) + (ch ^ 48); //作用同上一行语句
ch = getchar();
}
return s * w;
}当然快写函数还可以利用fread函数进行优化，优化如下
char buf[1 << 30], * p1 = buf, * p2 = buf; //buf存放字符数据，p1表示起点指针，p2表示终点指针
inline char _getchar() { //自己写的getchar
if (p1 == p2) {
p2 = buf + fread(buf, 1, 1 << 30, stdin); //读到哪，一个单字符字节大小，读多少，从哪里读，返回的是实际的终点
p1 = buf;
//以上两行语句可以合并成 p2=(p1=buf)+fread(buf,1,1<<21,stdin);
}
return *(p1++);
}使用fread函数之后只需要将第一版的快读函数中的getchar换成自己写的_getchar 就好。
快写函数就是将数字按位输出，函数体也是好理解的。
inline void write(int x) { //快写函数
if (x < 0) { //处理负数
putchar('-');
x = -x;
}
if (x > 9) write(x / 10); //递归调用
putchar(x % 10 + '0');
return;
}查找与删除
C++当中，map和set的底层是红黑树，查找的时间复杂度是O（logn），如果觉得该时间复杂度还是不够优秀，需要再优化时间复杂度时，可以考虑使用unordered_map或者unordered_set，其底层是散列哈希，查找时间复杂度在数据量较小的情况下可以到O（1），但是毕竟还是散列哈希，所以数据量太大的情况下查找的时间复杂度有可能会退化到O（n）。此外，假设需要在一个顺序表中进行O（logn）或者O（1）级别的定位删除，可以考虑使用 list 存储数据，利用 list 的链式存储特性，用一个map或者是unordered_map来维护 list 对应的迭代器，即：map<datatype, list<datatype>::iterator>或者unordered_map<datatype, list<datatype>::iterator>，而后若要删除数据，可以直接利用map构建的映射关系找到迭代器，迅速定位到要删除的元素并将其删除。
而在 Java 当中，LinkedHashMap 为我们提供了一个带有链表性质的哈希表，可以直接使用。如果不允许使用的话，因为Java 的语言限制，我们只好手撕双向链表，然后对 ListNode 进行维护。
前缀和
一维前缀和
定义两个数列{$a_n$}和{$S_n$}，数列{$S_n$}表示数列{$a_n$}的前n项和，其中有：
$$
S_n=\sum_{i=1}^{n}a_i
$$
记$S_{ij}$表示$a_i$到$a_j$的区间和，则有：
$$
S_{ij}=S_j-S_{i-1}
$$
二维前缀和
二维前缀和一般用于求解一个矩阵当中的某个子矩阵的元素和。
对于一个矩阵，利用$a_{ij}$表示矩阵当中第 i 行第 j 列的元素值，利用（i，j）表示矩阵第 i 行第 j 列的位置，F（i，j）表示从（1，1）到（i，j）的矩阵元素和。则有：
$$
F(i,j)=F(i-1,j)+F(i,j-1)-F(i-1,j-1)+a_{ij}
$$
而对于（x1，y1）到（x2，y2）的矩阵元素和E，则有：
$$
E=F(x_2,y_2)-F(x_2,y_1-1)-F(x_1-1,y_2)+F(x_1-1,y_1-1)
$$
矩阵压缩
矩阵压缩用于解决给出一个矩阵并求出子矩阵的元素和最值。在使用矩阵压缩时，使用到了“最大子段和”的思想。
最大子段和
最大子段和要求给定一个数组，并选出其中连续且非空的一段使得这段元素和最大。
这个问题的解决方法是使用动态规划的思想，记dp[i]为以该数组第 i 个元素结束的最大子段和，对于第 i 个元素，如果选择它能够使子段和增大，自然的我们要把它加入子段之中，如果加入后使得子段和变小，则子段的计算就以该元素开始重新计算，故我们可以很快得出状态转移方程：
$$
dp[i]=max(dp[i-1]+a[i],a[i])
$$
压缩矩阵
对于一个矩阵，进行压缩的步骤为：
按顺序使用 i 和 j 枚举矩阵的两行，对以 i 为上界，j 为下界的矩阵进行压缩。
压缩的时候按列求和，使用一个数组存储该子矩阵的各列元素和。
对该数组求最大子段和，当 i 和 j 的双重循环结束后，子矩阵的最大元素和就是求出的各最大子段和中的最大值。
代码如下（洛谷P1719）：
void Arr() {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
dp[i] = max(dp[i - 1] + a[i], a[i]);
ans = max(dp[i], ans);
}
}
void Matrix() {
for (int i = 1; i <= n; ++i) {
memset(a, 0, sizeof(a));
for (int j = i; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
a[k] += mp[j][k];
}
Arr();
}
}
}差分
定义两个数列{$a_n$}和{$d_n$}，数列{$d_n$}中的任意元素$d_i$表示$a_i$与$a_{i-1}$的差，即：
$$
d_n=a_n-a_{n-1}(其中a_0=0)
$$
差分与前缀和的关系
根据原数组、差分数组和前缀和数组的数学性质，我们不难得出它们的关系：
原数组进行差分得到差分数组，差分数组求前缀和得到原数组。
原数组求前缀和得到前缀和数组，前缀和数组进行差分得到原数组。
一维差分
差分适用于进行离线的区间修改，“离线”即为只能在完全对区间进行修改之后才能进行查询操作。
对于差分数组，如果我们想要将区间 [l，r] 上所有元素加 x，我们只需要对将$d_l+x$以及将$d_{r+1}-x$即可，最后我们将差分数组求其前缀和就可以得到我们要的区间修改了。
二维差分
二维差分更多的是对于一个矩阵的某个子矩阵的所有元素进行更改操作。
例如，我们利用 V（i，j）表示第 i 行第 j 列的元素，假设现在要对（x1，y1）到（x2，y2）的所有元素都加x，则差分矩阵可进行如下操作：
$$
v(x_1,y_1)+=x,v(x_1,y_2+1)-=x,v(x_2+1,y_1)-=x,v(x_2+1,y_2+1)+=x
$$
该操作证明不难，这里不作详细说明。
倘若我们要得到原矩阵，只需要对差分后的矩阵求其二维前缀和即可。
二分
二分可以分为二分查找和二分答案。有些时候题目需要我们进行判断最值，类似于求出某个满足题目条件的最大值或者最小值，这个时候我们可以考虑进行二分，使用O（logn）的复杂度来查找。而有时候题目会让我们求类似于最大的最小值或者最小的最大值，这个时候可以考虑二分答案，二分答案的时候需要满足答案具有单调性和有界性。
二分模板：
while (left <= right) { //left和right分别代表左边界和右边界，或者是下界和上界
int mid = left + (right - left) / 2; //防止溢出的小技巧
if (check(mid)) { //check函数，用来判断mid是否符合题意，不同题目有不同写法
left = mid + 1; //或者是right = mid - 1
ans = mid; //记录答案
}
else {
right = mid - 1; //或者是left = mid + 1
}
}
cout << ans;有时候需要精度更高的二分，有以下模板：
while (r - l >= 1e-5) { //精度更高的二分需要控制在1e-5上
double mid = l + (r - l) / 2.0; //使用double存储mid，注意除以2.0
if (check(mid)) {
ans = mid;
l = mid; //或者写成 r = mid
}
else {
r = mid; //或者写成 l = mid
}
}离散化
离散化，指把无限空间中有限的个体映射到有限的空间中去（这句话摘自百度百科，不得不说，还是有点抽象的），离散化是程序设计中比较实用的技巧，可以大幅度提升时空效率。离散化可以认为是一种哈希，记录了数字的相对大小，省去不需要使用的空间。
比如说，对于一个数组S = {1，1e4，99，1e6，99}，有些时候，为了哈希方便，我们可能不得不开一个长度为1e6的数组来方便我们作判断。但是，可以很直观的看出，S数组当中的数字数值跨度很大，特别是其中两个数字1e4和1e6，整整跨了两个数量级，这个时候我们开一个长度为1e6的数组来存储在空间上的浪费就很大。所以，我们可以利用离散化的思想来处理，我们把1记录为1，把99记录为2，把1e4记录为3，把1e6记录为4，则新数组S’ = {1，2，3，4}，换句话讲，新数组S’相对于S数组有三个优化：第一个是对数组进行排序；第二个优化是对S数组进行去重；第三个优化就是S’数组记录了S数组元素的相对大小，若要进行哈希，则可以对S’数组进行哈希，这个时候我们只需要开一个长度为4的数组即可。
在了解离散化的具体步骤之前，我们需要事先对两个操作进行详解：
去重（unique）
我们一般使用STL库当中的unique函数进行去重操作，使用的时候需要包含algorithm的头文件，并且需要保证数组是有序排列。
unique函数的作用是：去除数组当中相邻的重复元素（特别注意！！！正因为unique是去重相邻元素，所以如果要保证所有重复元素被去除，一定要保证数组是有序的！）
unique函数的原型有两个，分别为：
iterator unique（iterator it_1, iterator it_2）;
iterator unique（iterator it_1, iterator it_2, bool myCmp）;
注意这里的区间是左开右闭，即：[ it_1, it_2）
另外，unique函数的代码可以模拟成如下形式：
iterator My_Unique(iterator first, iterator last)//两个参数都是迭代器
{
if (first == last)
return last; // 只有一个元素的情况
iterator result = first; // 从第一个元素开始，result指针是用来覆盖原数组的
while (++first != last) // 直到最后一个元素
{
if (*result != *first) // 找到了一个不重复的元素
*(++result) = *first; // 覆盖前面的元素
}
return ++result; // 返回最后不重复元素的下一个元素的坐标的迭代器
}从函数原型和模拟代码中不难看出，unique函数返回的是一个迭代器，这是一个指向去重后不包含重复元素序列中最后一个元素的下一个元素的位置的迭代器。并且，去重的原理是直接对原数组进行数值上的覆盖，把没有重复的元素覆盖到数组前端来，并不是将重复的元素移到数组后端去，所以，实际数组的长度并没有发生改变。
假设有一个num[n]数组，我们现在使用unique对它进行去重，那么，我们利用unique返回迭代器的原理，利用如下代码可以获得去重后的数列的实际长度：
int len = unique(num, num + n) - num; //返回的迭代器减去初始地址，得到数组长度对于vector容器，有：
int len=unique(num.begin(),num.end())-num.begin(); //返回的迭代器减去初始地址，得到容器长度对于vector容器，我们还可以结合erase函数将容器的长度真正减少到去重后的实际长度：
num.erase(unique(num.begin(), num.end()), num.end()); //区间删除，删除unique返回的迭代器到容器真正末端迭代器的位置，这一段就是去重后理应废除掉的数组查找（lower_bound）
STL库当中的lower_bound函数可以帮助我们进行元素的查找，使用的时候需要包含algorithm的头文件。
函数原型有两个：
iterator lower_bound （iterator first，iterator last，const T& val）；
iterator lower_bound（iterator first，iterator last，const T& val，bool myCmp）；
第一个原型用于查找 [first，last）区间内 >= val 值的元素，第二个原型用于查找 [first，last）区间内第一个不满足myCmp规则的元素。函数返回的是该元素对应的迭代器。
该算法的底层逻辑是二分查找，故要求容器有序，时间复杂度为O（logn）。
离散化步骤
| 原数组： | ||||||
|---|---|---|---|---|---|---|
| 元素值 | 999 | 1 | 999 | 15 | 1000000 | 10000 |
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 排序： | ||||||
| 元素值 | 1 | 15 | 999 | 999 | 10000 | 1000000 |
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 去重： | ||||||
| 元素值 | 1 | 15 | 999 | 10000 | 1000000 | |
| 下标 | 0 | 1 | 2 | 3 | 4 | |
| 还原： | ||||||
| 元素值 | 999 | 1 | 999 | 15 | 1000000 | 10000 |
| 下标 | 2 | 0 | 2 | 1 | 4 | 3 |
离散化模板
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
int n;ll b;
vector<ll> tmp,all; //tmp是离散化数组，all是原数组
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> b;
tmp.push_back(b);
all.push_back(b);
}
sort(tmp.begin(), tmp.end()); //排序，保证数组有序
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); //去重，离散化
for (int i = 0; i < all.size(); ++i) {
int index = lower_bound(tmp.begin(), tmp.end(), all[i])-tmp.begin(); //当前迭代器减去begin得到具体离散化位置
cout << index +1 << ' ';
}
return 0;
}链表环的判定
链表环的判定一般使用快慢指针。根据追及原理易得，如果链表存在环，则快慢指针会在环中相遇。
设置两个指针，使得其中一个指针的遍历速度是2，另一个指针的遍历速度是1。设环的入口到表头的距离为 K，快慢指针在离环入口处 X 相遇，环的总长度为 X + Y。再假设快慢指针相遇前，慢指针在环中走了 n 圈，快指针在环中走了 N 圈。
则慢指针总距离为：$Distance_{slow} = K + n(X+Y)+X$
快指针总举例为：$Distance_{fast}=K+N(X+Y)+X$
二者走了相同时间，又$v_{fast}=2v_{slow}$，故$2Distance_{slow}=Distance_{fast}$
最终：$2K+2n(X+Y)+2X=K+N(X+Y)+X$
整理得：$K=(N-2n)(X+Y)-X$
该条式子中，N-2n 为整数，故当我们在快慢指针相遇后，将快指针重新放入表头并以相同的速度与慢指针同时遍历后，二者再次相遇的位置就是环入口。
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null) return null; //先对链表判空
ListNode fast = head, slow = head;
do {
if(fast == null) return null; //判空
fast = fast.next;
if(fast == null) return null; //判空，如果fast为null，表示链表没有环
fast = fast.next;
slow = slow.next;
} while(fast != slow);
ListNode p = head;
while(p != slow) { //p与慢指针同时遍历，相遇的时候就是链表环的入口
slow = slow.next;
p = p.next;
}
return p;
}
}原地哈希
一般用于对值域要求比较苛刻，需要找一组到数据范围0~n-1的映射，并且尽量减少冲突时，可以使用原地哈希。
原地哈希实际上时利用了废弃空间的一种原地算法。
例题：数组中重复的数据
题目描述：给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
思路：
- 交换位置：将每一个数都交换到对应的原本位置上，当交换位置产生冲突时，代表数据重复。
- 正负标记：与交换位置思路类似，这次利用负号表示该位置的元素被占用。相当于利用正负进行原地哈希。因为涉及到正负号，所以取值的时候需要注意调用
abs方法取绝对值。
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ansList = new ArrayList<>();
for(int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i]); //取数，注意abs取绝对值
if(nums[index - 1] > 0) {
nums[index - 1] *= -1; //负号标记，原地哈希
}
else {
ansList.add(index);
}
}
return ansList;
}
}