双指针是一种做题思路，并不隶属于某一种特定的数据结构，数组、链表、字符串都可以出双指针的题目
27. 移除元素【简单，快慢指针，首尾指针】-
快慢指针
-
首尾指针
class Solution {
public:
//快慢指针， 时间复杂度：O(n) 空间复杂度：O(1)
int removeElement(vector& nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
//双指针优化，避免了不必要的赋值
//首尾指针
//把等于val的值全部放到后面去
int removeElement01(vector& nums, int val) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
if (nums[left] == val) {
//nums[left] = nums[right];
swap(nums[left, nums[right]])
right--;
}
else {//不是需要删除的元素
left++;
}
}
return left;
}
};
26. 删除有序数组中的重复项【简单，快慢指针】
- erase暴力破解
- 快慢指针
class Solution {
public:
int removeDuplicates(vector& nums) {
if (nums.size() == 0) return 0;
int left = 0, right = 1;
for (right; right < nums.size(); right++) {
if (nums[right] != nums[left]) {
left++;
nums[left] = nums[right];
}
}
return left + 1;
}
};
844. 比较含退格的字符串【简单】
思路一：栈的压入和弹出
思路二：string容器实现栈的功能
class Solution {
public:
//时间复杂度：O(N+M)
//空间复杂度：O(N+M)
string build(string str) {
string ret;
for (char ch : str) {
if (ch != '#') {
ret.push_back(ch);
}
else if (ch=='#' && !ret.empty()) {
ret.pop_back();
}
}
return ret;
}
bool backspaceCompare(string S, string T) {
return build(S) == build(T); //比较两字符串相等
}
};
思路三：双指针，分别指向两个字符串
时间复杂度：O(n+m) m,n为两字符串长度
空间复杂度：O(1)
从后往前比较两个字符串
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0; //表示当前待删除的字符的数量
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] == '#') {
skipS++, i--;
}
else if (S[i] != '#' && skipS > 0) {
skipS--, i--;
}
else if (S[i] != '#' && skipS == 0) {
break; // 找到待比较的字符的索引
}
}
while (j >= 0) {
if (T[j] == '#') {
skipT++, j--;
}
else if (T[j] != '#' && skipT > 0) {
skipT--, j--;
}
else if (T[j] != '#' && skipT == 0) {
break; // 找到待比较的字符的索引
}
}
if (i >= 0 && j >= 0) {
if (S[i] != T[j]) return false;
i--, j--;
}
else if (i >= 0 && j < 0) return false; //bxj## bxj###
else if (i < 0 && j >= 0) return false;
}
return true;
}
};
977. 有序数组的平方【简单，首尾指针】
思路一：先for遍历换元，再sort排序；代码不记录
时间复杂度：O(NlogN) 空间复杂度：O(logN) 需要 O(logn) 的栈空间进行排序。
思路二：首尾指针，但需要容器，不能原地解
时间复杂度：O(logn) 空间复杂度：O(n)
class Solution {
public:
vector sortedSquares(vector& nums) {
vector v(nums.size(), 0); //初始化容器大小 和容器初始值
int left = 0, right = nums.size() - 1; //指向原来数组的首尾位置
for (int i = nums.size() - 1; i >= 0; i--) { //对容器中元素从后往前赋值
v[i] = abs(nums[left]) > abs(nums[right]) ? pow(nums[left++], 2) : pow(nums[right--], 2);
//if (abs(nums[left]) < abs(nums[right])) {
// v[i] = pow(nums[right], 2);
// right--;
//}
//else {
// v[i] = pow(nums[left], 2);
// left++;
//}
}
return v;
}
};
344. 反转字符串【简单】
题目意思：实现库函数reverse的功能
思路：首尾指针实现交换
class Solution {
public:
void reverseString(vector& s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
swap(s[i],s[j]);
}
}
};
剑指 Offer 05. 替换空格【简单，双指针】
思路一：使用额外辅助空间；重新生成一条字符串，不是空格就正常拼接字符串，是空格就拼接%20
时间复杂度：O(n)
空间复杂度：O(n)
思路二：不使用辅助空间
双指针实现；需要先扩容
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
string replaceSpace(string s) {
int count = 0; // 1.统计空格的个数
int sOldSize = s.size();
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
count++;
}
}
// 2. 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
s.resize(s.size() + count * 2);
int sNewSize = s.size();
// 3. 0从后先前将空格替换为"%20"
for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
if (s[j] != ' ') {
s[i] = s[j];
} else {
s[i] = '0';
s[i - 1] = '2';
s[i - 2] = '%';
i -= 2;
}
}
return s;
}
};
151. 翻转字符串里的单词【简单】
原地解法思路：
1.先去掉所有冗余空格
2.再整体反转字符串
3.再一个一个单词反转
步骤一种去空格我们不能用erase，因为erase的复杂度为O(n)
主要是明白上面的做题思路，还有会实现去空格的方法
class Solution {
public:
//函数一：反转字符串s中左闭右闭的区间[start, end]
void reverse(string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) { //首尾指针实现
swap(s[i], s[j]);
}
}
//函数二：移除冗余空格：使用双指针（快慢指针法）O(n)的算法
void removeExtraSpaces(string& s) {
int slow = 0, fast = 0; // 定义快指针，慢指针
for (fast; fast < s.size(); fast++) { //生成无多余空格的新字符串
if (s[fast] != ' ') {
s[slow] = s[fast];
slow++;
}
else if (fast - 1 >= 0 && s[fast - 1] != ' ' && s[fast] == ' ') {
s[slow] = ' ';
slow++;
}
}
if (slow - 1 > 0 && s[slow - 1] == ' ') { //检查字符串最末尾是不是空格
s.resize(slow - 1);
}
else {
s.resize(slow);
}
}
string reverseWords(string s) {
removeExtraSpaces(s); // 1.去掉冗余空格
reverse(s, 0, s.size() - 1); // 2.将字符串全部反转
int slow = 0;
int fast = 0;
for (fast; fast < s.size(); fast++) { //3.再反转各个单词
if (fast == s.size() - 1) { //处理最末尾一个单词
reverse(s, slow, fast);
return s;
}
if (s[fast] == ' ') {
reverse(s, slow, fast - 1);
slow = fast + 1;
}
}
return s;
}
};
206. 反转链表【简单】
思路一：栈
倒序反转的最适合栈；可以存储val值，也可以存储结点；然后重新生成一条链表。
思路二：使用双指针修改指向
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
//双指针实现修改指向 下一个指向前一个
ListNode* reverseList(ListNode* head) {
ListNode* fast = head; //快指针指向头结点 慢指针指向头结点的前一个结点，即NULL
ListNode* slow = NULL;
while (fast != nullptr) {
ListNode* next = fast->next;
fast->next = slow; //核心代码，修改指向
slow = fast; //前移两个指针
fast = next;
}
return slow;
}
};
思路三：递归套娃
时间复杂度：O(n)
空间复杂度：O(n)； 取决于递归调用的栈空间
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);
}
};
19.删除链表的倒数第N个节点【简单】
思路一：使用vector容器存结点，索引找到待删除节点的前一个结点，修改指向
思路二：使用栈的压入和弹出，翻转就要想到栈
思路三：两次遍历，第一次遍历计数，第二次遍历实现删除
思路四：快慢双指针；使得两指针维持一定间隔，当快指针指向空结点时，慢指针指向需要删除的结点的前一个结点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* start = new ListNode(0, head); //1.head前面生成一个结点
ListNode* fast = head;
ListNode* slow = start;
for (int i = 0; i < n; ++i) { //2.移动快指针 使得 fast-slow 中间隔了n个结点
fast = fast->next;
}
while (fast) { //3.快速移动fast指向最后
fast = fast->next;
slow = slow->next;
} //fast指向null时 slow结点是需要删除结点的前一个结点
slow->next = slow->next->next; //4.删除节点
ListNode* res = start->next;
delete start;
return res;
}
};
160. 相交链表【简单】
相同题目：剑指 Offer 52. 两个链表的第一个公共节点
相同题目：面试题 02.07. 链表相交
思路一：双栈
自己实现了这个
思路：两条链表后面的结点肯定是相同的，我们倒序找到最后一个相同的结点。
实现倒序就要用到栈
class Solution {
public:
//双栈
//时间复杂度：O(m+n) 遍历两链表
//空间复杂度：O(m+n) 存入两链表
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
stack sA;
stack sB;
if (headA == nullptr || headB == nullptr) return NULL; //排除特殊情况
auto nodeA = headA; //1.两条链表入两个栈
while (nodeA != nullptr) {
sA.push(nodeA);
nodeA = nodeA->next;
}
auto nodeB = headB;
while (nodeB != nullptr) {
sB.push(nodeB);
nodeB = nodeB->next;
}
if (sA.top() != sB.top()) return NULL; //两链表最后一个数都不相同 就没有交集
int sizeMin = min(sA.size(), sB.size());
while (sizeMin != 0) {
if (sA.top() == sB.top()) {
sA.pop();
sB.pop();
}
else {
return sA.top()->next; //2.找到交集的起始结点
}
sizeMin--;
}
return sA.size() > sB.size() ? headB : headA; //while循环没else语句跳出 则其中短的链表就是交集 所以返回它的起始结点
}
};
思路二：哈希表存链表A的结点；然后遍历查找链表B的结点
class Solution {
public:
//哈希表也能实现功能
//时间复杂度：O(m+n) mn分别为两链表的长度 因为需要遍历两链表
//空间复杂度：O(m) 一链表的长度
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
unordered_set set;
ListNode* nodeA = headA; //1.先把链表A的结点全部存入
while (nodeA) {
set.insert(nodeA);
nodeA = nodeA->next;
}
auto nodeB = headB;
while (nodeB) {
if (set.count(nodeB)) return nodeB;//2.在哈希表中查找链表B的结点 查到则返回
nodeB = nodeB->next;
}
return NULL; //3.没查到，说明没有交集
}
};
思路三：双指针，浪漫的相遇
具体思路看此人的动图演示：链接
空间复杂度：O(1)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *node1 = headA;
ListNode *node2 = headB;
while (node1 != node2) {
node1 = node1 != NULL ? node1->next : headB;
node2 = node2 != NULL ? node2->next : headA;
}
return node1;
}
};
思路四：对齐链表右边，再遍历
时间复杂度：O(1)
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在同一起点上（末尾位置对齐）
for(int i = 0; i < gap; i++){
curA = curA->next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) return curA;
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
141. 环形链表【简单，哈希表，双指针】
升级版本题目：142. 环形链表 II
题目意思：给你链表判断是否有环
思路一：哈希表
//时间复杂度：O(n) //空间复杂度：O(n) 多余容器空间
思路二：双指针
快指针走两步，慢指针走一步
正版双指针思路：https://leetcode-cn.com/problems/linked-list-cycle/solution/dai-ma-sui-xiang-lu-141-huan-xing-lian-b-h1jq/
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ev3rtmxh-1641285737384)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112201804347.gif)]
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==nullptr || head->next==nullptr) return false; //排除0,1结点情况
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next; //慢指针走一步 快指针走两步 相遇证明有环
fast = fast->next->next;
if (slow == fast) return true; // 快慢指针相遇，说明有环
}
return false; //能走到NULL说明就没环
}
};
142. 环形链表 II【中等】
思路一：哈希表
与上一题相比，只是修改了返回值
时间复杂度：O(n)
空间复杂度：O(n)
思路二：快慢指针，慢的走一步，快的走两步
就是这个难，可以结合官方讲解和代码随想录的一起学习
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QyEV3JHB-1641285737385)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112201804380.gif)]
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
if (slow == fast) { //有环，寻找环的入口
ListNode* index1 = fast; //一个从head开始，一个从相交点开始
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2; // 返回环的入口
}
}
return NULL; //无环遍历到底端
}
};
15. 三数之和【中等，双指针】
思路：排序+双指针
哈希表时间复杂度和空间复杂度都很高；难度主要在于降重
时间复杂度：O(n^2)
空间复杂度：O(1)
class Solution {
public:
vector> threeSum(vector& nums) {
vector> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0 a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组
if (nums[i] > 0) return result;
// 正确去重方法
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
if (nums[i] + nums[left] + nums[right] > 0) {
right--;
}
else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
}
else {
result.push_back(vector{nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个三元组之后
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
return result;
}
};
18. 四数之和【中等】
与上一题思路一样
class Solution {
public:
vector> fourSum(vector& nums, int target) {
vector> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// 去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 正确去重方法
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
right--;
}
else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) {
left++;
}
else {
result.push_back(vector{nums[k], nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个四元组之后
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};
