数组双指针法
双指针法也叫快慢指针法，在数组和链表中利用双指针法可以高效解决很多问题
双指针法的关键在于把两次循环合并为一次，很多暴力算法都可以用双指针法来优化
目录不多说，直接上题ヾ(≧▽≦*)o
刷题顺序来自《代码随想录》，自己整理下总结
leetcode相关题目
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
这道题可以通过设置一个新的数组，遍历一边原数组，将不等于val的元素放入新数组中，时间复杂度为 O(n) , 空间复杂度为 O(n) , 但是题目要求只能使用 O(1) 的空间，也就是得在原数组上操作。
-
暴力解法 O(n^2)
遍历数组， 每遇到等于 val 的元素， 删除该元素，后面元素前移
class Solution { public: int removeElement(vector<int>& nums, int val) { int length = nums.size(); for (int i = 0; i < length; i++) { if (nums[i] == val) { for (int j = i; j < length - 1; j++) { nums[j] = nums[j + 1]; } length -= 1; i--; //关键，容易写漏，下标整体前移 } } return length; } };这个暴力方法还可以优化一下，从后往前遍历，可以减少元素前移的次数，但是时间复杂度依旧是O(n^2)
如数组 [3, 2, 2, 3] ，val = 2，从前往后遍历删除，我们要移动 [3, 2, 2, 3] (2次) + [3, 2, 3] (1次) = 3 次
从后往前遍历，我们要移动 [3, 2, 2, 3] (1次) + [3, 2, 3] (1次) = 2 次 , 移动次数减少了，因为我们对要删除的重复元素的移动减少了。
-
双指针法 O(n)
定义一个快指针 fastIndex 来遍历数组， 慢指针 slowIndex 指向要更新的数组位置，当 fastIndex 指向的元素和要删除的元素不同时，更新到 slowIndex 位置上，slowIndex 移动一位
class Solution { public: int removeElement(vector<int>& nums, int val) { int slowIndex = 0, fastIndex = 0; //初始化快慢指针 while (fastIndex < nums.size()) { //快指针遍历 if (nums[fastIndex] != val) { nums[slowIndex] = nums[fastIndex]; slowIndex++; } fastIndex++; } return slowIndex; //slowIndex指向下一位下标，slowIndex 就是长度 } };
26. 删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
因为数组是有序的，我们可以用双指针法来删除重复元素，让 slowIndex 指向前一个元素 ，fastIndex 遍历 ，如果 fastIndex 指向的值和slowIndex 指向的值相同时，说明重复了，slowIndex 不动，fastIndex 移动一位；否则，就先让 slowIndex 指向下一位，然后更新。
要注意与上一题的区别是，这里 slowIndex 指向的是已经被更新的数组位置，而不是要被更新的位置，所以最后返回长度的时候要 +1
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) return 0;
int slowIndex = 0, fastIndex = 0;
while (fastIndex < nums.size()) {
if (nums[fastIndex] != nums[slowIndex]) {
slowIndex++; //slowIndex 要先加一
nums[slowIndex] = nums[fastIndex];
}
fastIndex ++;
}
return slowIndex + 1; //返回长度要加一
}
};
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
相当于把元素中为 0 的元素删除然后在末尾添加0
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int fastIndex = 0, slowIndex = 0;
for (; fastIndex < nums.size(); fastIndex++) { //删除为0的元素
if (nums[fastIndex] != 0) {
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
for (int i = slowIndex; i < nums.size() ; i++) { //末尾添加0
nums[i] = 0;
}
}
};
844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 “”。
示例 3：
输入：s = "a##c", t = "#a#c"
输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
-
一种方法是把两个输入都先转换成对应的字符串，这里就用到栈的数据结构，然后再比较字符串大小
时间复杂度O(N)
空间复杂度O(N)
class Solution { public: bool backspaceCompare(string s, string t) { string s1, s2; int index1 = 0, index2 = 0; for (int i = 0; i < s.length(); i++) { //利用string的栈特性把s转化成对应字符 if (s[i] != '#') { s1 += s[i]; } else if (!s1.empty()) { s1.pop_back(); } } for (int i = 0; i < t.length(); i++) { //利用string的栈特性把t转化成对应字符 if (t[i] != '#') { s2 += t[i]; } else if (!s2.empty()) { s2.pop_back(); } } if (s1.compare(s2) == 0) { //比较字符串 return true; } return false; } }; -
利用双指针，这里的双指针不是前面提到的指向一个数组中快慢指针了，而是一个指针指向字符串 s ， 一个指针指向字符串 t，然后逐个比较。
在比较普通的字符串时，如字符串 “abc” 和 “abd” ，我们依次比较每个位置的字符是否相等，也就是说本质上只有一个下标在变化。
但是这道题目字符串中含有特殊字符 “#” 表示退格，这样我们比较两个字符串时就不能用相同的下标了，所以就有了两个不同指针，也可以说是两个快慢不同的指针。
那我们怎么确定两个指针的速度呢，就是通过字符串中的 “#” 符号，先要确定 “#” 的个数，才能定位两个指针分别要移动的位置，所以指针要从后往前遍历。
时间复杂度O(N)
空间复杂度O(1)
这里很容易犯错误，我一开始就很自然从后往前先统计 “#” 的个数，然后让指针一次性移动相应次数，比较此时字符是否相等。这时会存在特殊情况那就是，退格后指向的字符串还是退格，就会出错。例如 "ab##" 和 "c#d#" ，前者指向 ‘b'，后者指向 ’#‘，返回false，实际应返回true。解决办法就是每次退格后都要判断当前的字符是不是 “#” ，是的话继续退格。
class Solution { public: bool backspaceCompare(string s, string t) { int index1 = s.size() - 1, index2 = t.size() - 1; //初始化两个 “指针” ,分别指向两个字符串的末尾 int skips = 0, skipt = 0; //退格次数 while (index1 >= 0 || index2 >= 0) { //当两个字符串都没全遍历完时 while (index1 >= 0) { if (s[index1] == '#') { //当前字符是退格符，退格数+1 skips++; index1--; } else if (skips > 0) { //退格数不为0，退格 index1--; skips--; } else { //当前字符不是退格符，且退格数为0，说明当前指向的字符就是要比较的字符 break; } } // 字符串t处理同理 while (index2 >= 0) { if (t[index2] == '#') { //当前字符是退格符，退格数+1 skipt++; index2--; } else if (skipt > 0) { //退格数不为0，退格 index2--; skipt--; } else { //当前字符不是退格符，且退格数为0，说明当前指向的字符就是要比较的字符 break; } } //下面是错误的写法 //一开始就很自然从后往前先统计 “#” 的个数，然后让指针一次性移动相应次数 // while (s[index1] == '#') { // skips++; //遇到退格，退格数+1 // index1--; // } // if (skips > 0) { //退格数大于0，退格相应数量，重置退格数 // index1 -= skips; // skips = 0; // } // while (t[index2] == '#') { // skipt++; //遇到退格，退格数+1 // index2--; // } // if (skipt > 0) { //退格数大于0，退格相应数量，重置退格数 // index2 -= skipt; // skipt = 0; // } if (index1 >= 0 && index2 >= 0) { //此时 index1 和 index2 都指向要比较的字符 if (s[index1] != t[index2]) { //字符不相等，返回false return false; } } else if (index1 >= 0 || index2 >=0){ //两个字符串一个遍历完，一个没遍历完，返回false return false; } index1--, index2--; } return true; //此时，两个字符串都遍历完 } };