6.12.双指针专题

27. 移除元素

题意描述：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

思路：

定义快慢指针fast、slow，fast记录新数组元素，slow记录新数组下标。

AC代码：

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;for(int fast = 0 ; fast < nums.size() ; fast ++){if(nums[fast] != val)  nums[slow++] = nums[fast];}return slow;}
};

---

344.反转字符串

题意描述：

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

思路：

定义双指针i 从左边开始遍历、j从右边开始遍历，每次交换字符元素。

AC代码：

class Solution{public:void reverseString(vector<char>& s){for(int i = 0 , j = s.size() - 1 ; i < s.size() / 2 ; i ++ , j --)   swap(s[i] , s[j]);}
};//函数是void，故不用return

---

替换数字

题意描述：

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

思路：

先统计原字符串s中数字的个数cnt ， 将s扩容到目标大小，即 s.size() + 5 * cnt，然后定义新旧指针（我这里用的快慢）分别指向新旧字符串数组的最后一个元素，如果遇到数字，新数组倒序输入number,其他情况复制旧数组元素到新数组。

AC代码：

#include<iostream>
using namespace std;int main(){string s;cin >> s;int  n = s.size(), cnt = 0;for(int fast = 0 ; fast < n ; fast++){if(s[fast] >= '0' && s[fast] <= '9')  cnt++;}s.resize( n + 5 * cnt);for(int fast = s.size() - 1 , slow = n - 1; slow >= 0 ;slow -- ){if(s[slow] >= '0' && s[slow] <= '9'){s[fast --] = 'r';s[fast --] = 'e';s[fast --] = 'b';s[fast --] = 'm';s[fast --] = 'u';s[fast --] = 'n';}else {s[fast --] = s[slow]; }}cout << s;
}

其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

1. 不用申请新数组。
2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

---

M:151.翻转字符串里的单词

题意描述：

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

思路：

1. 去除多余空格，思路与移除元素相同，val = ‘ ’；
2. 用reverse函数将整个字符串翻转
3. 翻转单词

AC代码：

removeExtraSpaces函数，从去除前面，中间，后面空格的顺序来写。

//版本一 void removeExtraSpaces(string& s){int slow = 0, fast = 0;// 去掉字符串前面的空格while(s.size() > 0 && fast < s.size() && s[fast] == ' ')  fast ++;// 去掉字符串中间部分的冗余空格for( ; fast < s.size() ; fast++){if(fast - 1 > 0 && s[fast - 1] == s[fast] && s[fast] == ' ')  continue;else  s[slow ++] = s[fast];}//后面此时最多有一个空格,重新设置字符串大小if(slow - 1 > 0 && s[slow - 1] == ' ')  s.resize(slow - 1)else s.resize(slow);} 

// 版本二 
void removeExtraSpaces(string& s){int slow = 0;for(int fast = 0 ; fast < s.size() ; fast ++){//遇到非空格就处理,否则跳出到下一吃循环,这里删除了所有空格。if(s[fast] != ' '){//给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。if(slow != 0) s[slow ++] = ' ';//补上该单词，遇到空格说明单词结束。while(fast < s.size() && s[fast] != ' ')  s[slow ++] = s[fast ++];}}//slow的大小即为去除多余空格后的大小。s.resize(slow);} 

整体代码：

class Solution{public:/*翻转，区间写法：左闭右闭 []void reverse(string& s , int start , int end){for(int i = start , j = end ; i < j ; i ++ , j --)  swap(s[i] , s[j]);}我这里用库函数reverse*/void removeExtraSpaces(string& s){int slow = 0;for(int fast = 0 ; fast < s.size() ; fast ++){//遇到非空格就处理,否则跳出到下一吃循环,这里删除了所有空格。if(s[fast] != ' '){//给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。if(slow != 0) s[slow ++] = ' ';//补上该单词，遇到空格说明单词结束。while(fast < s.size() && s[fast] != ' ')  s[slow ++] = s[fast ++];}}//slow的大小即为去除多余空格后的大小。s.resize(slow);} string reverseWords(string s) {//去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。removeExtraSpaces(s);reverse(s.begin() , s.end());//STL中reverse函数是左闭右开//removeExtraSpaces后保证第一个单词的开始下标一定是0。int start = 0;for(int i = 0 ; i <= s.size() ; i++){//到达空格或者串尾，说明一个单词结束。进行翻转。if(i == s.size() || s[i] == ' ') {//翻转，注意是左闭右闭 []的翻转。start ~ i - 1reverse(s.begin() + start , s.begin() + i);//更新下一个单词的开始下标startstart = i + 1;}}return s;}
};

---

206.反转链表

题意描述：

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路：

只需改变next指针朝向，原地翻转即可，定义pre ， cur ， tmp 指针分别指向 前， 现在， 下 节点。

AC代码：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* tmp; // 保存cur的下一个节点ListNode* cur = head;ListNode* pre = NULL;while(cur) {tmp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur->next = pre; // 翻转操作// 更新pre 和 cur指针pre = cur;cur = tmp;}return pre;}
};

另解：递归法

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。

关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head``，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。

具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。

class Solution {
public:ListNode* reverse(ListNode* pre,ListNode* cur){if(cur == NULL) return pre;ListNode* temp = cur->next;cur->next = pre;// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步// pre = cur;// cur = temp;return reverse(cur,temp);}ListNode* reverseList(ListNode* head) {// 和双指针法初始化是一样的逻辑// ListNode* cur = head;// ListNode* pre = NULL;return reverse(NULL, head);}};

• 时间复杂度: O(n), 要递归处理链表的每个节点
• 空间复杂度: O(n), 递归调用了 n 层栈空间

我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。

具体代码如下（带详细注释）：

class Solution {
public:ListNode* reverseList(ListNode* head) {// 边缘条件判断if(head == NULL) return NULL;if (head->next == NULL) return head;// 递归调用，翻转第二个节点开始往后的链表，这一步仔细体会ListNode *last = reverseList(head->next);// 翻转头节点与第二个节点的指向head->next->next = head;// 此时的 head 节点为尾节点，next 需要指向 NULLhead->next = NULL;return last;}
}; 

---

19.删除链表的倒数第N个节点

题意描述：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1 输出：[]

示例 3：

输入：head = [1,2], n = 1 输出：[1]

思路：

定义双指针fast 、 slow ，先让fast走n + 1 步 ，然后fast 、 slow同时走，fast走到结尾时，slow的下一个元素恰好是待删除元素，此时令 slow-> next = slow -> next -> next即可。

AC代码：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;//while(n --)执行顺序说明：先判断n>0? 如果是则 -1while(n-- && fast != NULL) {fast = fast->next;}fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点,结合上面的图可以理解，这一步很重要while (fast != NULL) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next; // ListNode *tmp = slow->next;  C++释放内存的逻辑// slow->next = tmp->next;// delete tmp;return dummyHead->next;}
};

---

面试题 02.07. 链表相交

题意描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

[

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

[

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

[

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

思路：

定义双指针curA 、curB , 目前curA指向链表A的头结点，curB指向链表B的头结点,计算AB链表长度差gap假如lenA > lenB（如果不是就swap（lenA，lenB）, swap(curA , curB)。让curA先走gap步，然后curA、curB同时走到末尾，过程中比较指针是否相等即可。

AC代码：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lenA = 0, lenB = 0;while (curA != NULL) { // 求链表A的长度lenA++;curA = curA->next;}while (curB != NULL) { // 求链表B的长度lenB++;curB = curB->next;}curA = headA;curB = headB;// 让curA为最长链表的头，lenA为其长度if (lenB > lenA) {swap (lenA, lenB);swap (curA, curB);}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上（末尾位置对齐）while (gap--) {curA = curA->next;}// 遍历curA 和 curB，遇到相同则直接返回while (curA != NULL) {if (curA == curB) {return curA;}curA = curA->next;curB = curB->next;}return NULL;}
};

---

M:142.环形链表II

题意描述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

思路：

主要考察两知识点：

• 判断链表是否环
• 如果有环，如何找到这个环的入口

1. 判断是否有环

定义快慢指针fast 、slow， fast每次走两步 ， slow 每次走一步 ， 若循环中相遇则有环。

2. 环的入口

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

取n为1，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

AC代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;//这里的判断条件是fast和fast->next不为空while(fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇。上面推导n = 1的情况。if (slow == fast) {ListNode* index1 = fast;ListNode* index2 = head;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index2; // 返回环的入口}}return NULL;}
};

---

M:第15题. 三数之和

题意描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

思路：

滑动窗口思想，先排序数组，然后去重处理。一层for循环控制i遍历整个数组，然后定义双指针l、 r分别在nums[i] + nums[l] + nums[j] < 0 和 > 0时右滑/左滑。如果三数之和=0，则保存进res，然后去重处理处理，将r左移、l右移。

代码注意的几点：

• 结果返回的是[] 、[]的三元组形式，故定义res为二重数组vector<vector<int>>,然后在res.push_back的时候，参数是{vector<int>{nums[i] , nums[l] , nums[r]}}
• else的逻辑，在三数之和 = 0时需将左右窗口分别移动，else push_back那里括号较多，应分行写。
• res的return在for循环之后，写完要检查

AC代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin() , nums.end());for(int i = 0 ; i < nums.size() ; i++){if(nums[i] > 0)  return res;if(i > 0 && nums[i] == nums[i - 1]) continue;int l = i + 1 , r = nums.size() - 1;while(r > l){if(nums[i] + nums[l] + nums[r] > 0) r--;else if(nums[i] + nums[l] + nums[r] <0) l++;else {res.push_back(vector<int>{nums[i] , nums[l] , nums[r]});while(r > l && nums[r] == nums[r - 1])  r--;while(r > l && nums[l] == nums[l + 1])  l ++;r --;l ++;}}   }return res;}
};

---

第18题. 四数之和

题意描述：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

思路：

四数之和，和三数之和 是一个思路，都是使用双指针法, 基本解法就是再套一层for循环。

但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

类似的二级剪枝：nums[i] + nums[j] > target && (nums[i] + nums[j] >= 0)

去重操作还是一样的。

三数之和 的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n²)，四数之和的时间复杂度是O(n³) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

AC代码：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;sort(nums.begin() , nums.end());for(int i = 0 ; i < nums.size() ; i++){// 剪枝处理if(nums[i] > target && nums[i] >= 0)  break;// 这里使用break，统一通过最后的return返回// 对nums[i]去重if(i > 0 && nums[i] == nums[i - 1]) continue;for(int j = i + 1 ; j < nums.size() ; j++){// 二级剪枝处理if(nums[i] + nums[j] > target && nums[i] + nums[j] >= 0)  break;// 对nums[i]去重if(j > i + 1 && nums[j] == nums[j - 1])  continue;int l = j + 1 , r = nums.size() - 1;while(r > l){// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出if((long)nums[i] + nums[j] + nums[l] + nums[r] > target) r--;else if((long)nums[i] + nums[j] + nums[l] + nums[r] < target) l++;else {res.push_back(vector<int>{nums[i] , nums[j] , nums[l] , nums[r]});// 对nums[left]和nums[right]去重while(r > l && nums[r] == nums[r - 1])  r--;while(r > l && nums[l] == nums[l + 1])  l ++;// 找到答案时，双指针同时收缩r --;l ++;}}}
}return res;}
};