本节都是简单题，但仍然有它们的魅力所在。
（一）LeetCode26：遇见本题，也许你的做法是：（没错，这就是我开始的做法，但。。。超时了）
class Solution {
public:
int removeDuplicates(vector& nums) {
if(nums.empty()) return nums.size(); // 判空条件一定要写啊
int count = 0;
for(int i = 0; i < nums.size() - count - 1; i ++) { // 由于数组是有序的，我们才可以这样做
if(nums[i] != nums[i + 1]) continue;
else {
for(int j = i + 1; j < nums.size() - count; j ++) {
nums[j - 1] = nums[j];
}
count ++; // count用于记录，有一个重复被去掉了
i --; // i--是因为数组往前移位了一格
}
}
return nums.size() - count;
}
};
更加优质的做法：（上面使用了双指针的思想）
先分析一下，本题告诉我们“有序数组”有什么用？这告诉我们相同元素一定是相邻的；
原地算法，指的是不能新开数组，不能用递归。
本题更优质的算法仍然是双指针算法，本题是一道经典的双指针问题，c++中的unique函数就是如下实现的。
再分析一下，上面思路时间复杂度高的原因其实是因为每次遇到不同的数都要所有数组往前覆盖一位，这样很费时间。
现给出更优质的双指针算法：
一个指针一直往后遍历（用来找unique的数），另一个指针用来将上一个指针遍历过程中发现的与上一个数不同的数依次顺序地覆盖到现数组中的一个个格子中。
还是很懵，上代码：
class Solution {
public:
int removeDuplicates(vector& nums) {
if(nums.empty()) return nums.size(); // 判空条件一定要写啊
int j = 0;
for(int i = 0; i < nums.size(); i ++) { // 由于数组是有序的，我们才可以这样做
if(!i || nums[i] != nums[i - 1]){ // 如何处理第一个元素，这里使用了‘或’运算符！（因为第一个运算符没有前一个元素）
nums[j ++] = nums[i]; // 相当于在原数组的基础上覆盖
}
}
return j;
}
};
【注】本算法时间复杂度为2n，即O(n)
（二）LeetCode27：移除元素本题与上一题非常类似，同时比上一题还简单，也是双指针，而且确定了你要移除的元素，这里就不多讲了
class Solution {
public:
int removeElement(vector& nums, int val) {
int j = 0;
for(int i = 0; i < nums.size(); i ++) {
if(nums[i] == val) continue; // 这里就是遇到val跳过它就可以了
else nums[j ++] = nums[i];
}
return j;
}
};
（三）LeetCode28：实现 strStr()
开始的思路是，双指针，外部的指针一直在haystack上往后遍历，当在haystack中遇见以needle为首字母的字符时就停下来看看是否匹配，这时进入内层循环，比较在needle的长度限制下是否完全匹配。
然而，这一思路又是该死的“超出时间限制”了(灬ꈍ ꈍ灬)，没办法只能另寻它路。
开始的代码示例：
class Solution {
public:
int strStr(string haystack, string needle) {
if (haystack.size() < needle.size()) return -1;
if (needle == "") return 0;
int flag = 0, temp;
for (int i = 0; i < haystack.size(); i++) {
temp = i;
if (haystack[i] == needle[0]) {
for (int j = 0; j < needle.size(); j++) {
cout << needle[j] << haystack[i] << endl;
if (needle[j] != haystack[i ++]) break;
if (j == needle.size() - 1) return temp;
}
}
i = temp;
}
return -1;
}
};
有过算法经验的同学，也许就会发现，本题就是非常典型的kmp啊，而且就是kmp的母题了。在此之前，先重新了解一下kmp算法：
题目：给定一个模式串 s，以及一个模板串 p，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
现题目给了两个数组，一个是s，一个是p，s为原串，p是目标串，怎么考虑它们的匹配问题：（先想两个问题：1. 暴力循环怎么做？ 2. 如何去优化）
暴力做法伪代码：（朴素做法）
s[n], p[m]
for(int i = 1; i <= n; i ++) { // 字符串的处理从1开始，在一些边界判断上，更加符合我们的认知
bool flag = true
for(int j = 1; j <= m; j ++) {
if(s[i + j - 1] != p[j]) { // 这里其实就是在内部匹配的时候，外面的串随着j++也要同时移动，否则就一直是i在那里固定不动地进行比较了。- 1是因为j是从1开始遍历的！
flag = false;
break;
}
}
}
优化之前要注意的两个点
①. kmp的字符串都是从1开始（从1开始更利于字符串使用时的理解），所以在使用之前要处理一下：
s = ’ ’ + s, p = ’ ’ + p;
②. kmp中有一个核心的数组 next数组： next [ i ] ，搞清楚了next[ i ]的含义就好办了。
next[ i ] ：在模板串p中以1开始，以i结尾的子串中，某个前缀与某个后缀相等时的长度的最大值
（当然，不考虑平凡的前缀和后缀，即不应考虑p本身）
kmp匹配算法共分为两个过程，一个是求前后缀相等时的最大长度的next[i]数组，还有一个进行匹配的过程。
为什么要有这两个过程呢？下面说一下整个过程：
如果发现 j + 1不能匹配了，那就将 j 赋值为next[j]，即下标 j 变为长度 next[j]，为什么可以这样？因为p是从1开始的，当子串以j结束时，其前后缀和相等的最大值就是 next[j]，故此时 next[j] 前面的所有元素都是和s匹配的，所以当然可以将j下标变为next[j] ！！！
听了以上的讲解，现在你应该知道原因了吧，我们要先找到最长的那个next数组，然后再去从前往后匹配
（一）现在我们先了解一下求next数组的过程，举个栗子：
令 s = ""， p = "abababab"，next为p中前缀等于后缀时的最大长度： next[1] = 0 // 一个元素a，没人和其匹配 next[2] = 0 // a和b不等，而自己也不能和自己匹配，即：长度一定要小于自己 next[3] = 1 // 最大的前缀和后缀为"a", 故为1 next[4] = 2 // 为 "ab"，故长度为2 next[5] = 3 // 为 "aba"，故长度为3 next[6] = 4 // 为 "abab" ，故长度为4 next[7] = 5 // 为 "ababa" ，故长度为5 ......
当然，求next[j]时要注意一下边界情况，即next[1] == 0，因为我们要去除非平凡的情况！
（二）看完了求next数组的过程，现在我们来看看字符串匹配的过程：
求出了next数组，匹配的过程就轻松了，逐一匹配，一旦发现不匹配就 j = next[j]回到正确的位置，匹配就j ++，知道 j 等于p的长度m就返回。将s下标从1开始，p下标从0，当然，从1开始也可以，不过要修改一些特判条件。
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0; // 特判条件
int n = haystack.size(), m = needle.size(); // size为数组中元素个数
haystack = ' ' + haystack, needle = ' ' + needle; // 下标从1开始，这样更符合认知，后面处理下标时更方便，当然，这是个人习惯问题
vector next(m + 1); // next数组长度为m + 1，因为现在needle从0开始共m+1个数，前面加了一个空格是第0个元素
// 求next数组:求next数组是只针对needle的，求前缀与后缀相等的最大值（求出来后在匹配时会使用），与haystack无关
// 循环中i为控制变量，由于next[0]和next[1]都是0（要忽略平凡的情况，因为本身与本身相等不算）.所以i从2开始遍历
for(int i = 2, j = 0; i <= m; i ++) { // 等于是因为needle共有m+1个数，当等于m时，计数变量i停止
// 上来先判断中止的情况，即图中的i与j不等，前后缀长度中止增长，此时要让前后缀缩短一些
while(j && needle[i] != needle[j + 1]) j = next[j]; // i与j错开一位模拟了前后缀，j为前缀的开头，i为后缀的开头，如果i往后遍历时，发现不相等，那么j就要向后移动，移动的位置为它的next数组对应的长度，next[j]前面的所有元素一定都是匹配成功了的
if(needle[i] == needle[j + 1]) j ++;
next[i] = j; // 上面如果匹配失败，那么next[i]就还是上一个j的长度；如果匹配成功，那么next长度就加1了
}
// 下面是haystack与needle匹配的过程，i为h的计数变量；j为n的计数变量
for(int i = 1, j = 0; i <= n; i ++) { // j从0开始，是为了 更方便的计算已经匹配成功的长度
while(j && haystack[i] != needle[j + 1]) j = next[j]; // 遇见匹配失败的就将j指针减小到next[j]，next[j]之前的一定都是匹配成功的，不用再重新去匹配的，只需i继续++与p串匹配即可
if(haystack[i] == needle[j + 1]) j ++; // 匹配成功就j长度++
if(j == m) return i - m;// 匹配成功的整个串在haystack的起始位置为i-m
}
return -1;
}
};
①. 上面两个循环中标识符i与j的初始值辨析：第一个循环要求i与j间隔一个，而第二个循环则是相同位置逐个匹配。
②. 其中让字符串从第1个字符串的方法：p = ’ ’ + p // 当然也可以；p = " " + p ，注意空格要加在前面，否则加在末尾就没有意义了
③. 找next数组和匹配的过程都用到了while循环，该循环不是只动一次的，如果一直不相等，那么就一直执行 j = next[j]，最坏的情况是所有都不等，那么因为 j 为2时，next[j] 为0 或1，0赋给j就退出循环，而1赋给j，next[1] 也是0 （定义时vector时被初始化为0），不等也当然是直接退出循环 ！
④. j + 1是很有讲究的，如果条件符合j才真正 ++，否则还原；
