双指针法
双指针是一种做题思路，并不隶属于某一种特定的数据结构，数组、链表、字符串都可以出双指针的题目
27. 移除元素【简单，快慢指针，首尾指针】
- 快慢指针
- 首尾指针
class Solution { public: //快慢指针， 时间复杂度：O(n) 空间复杂度：O(1) 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]; slow++; } } return slow; } //双指针优化，避免了不必要的赋值 //首尾指针 //把等于val的值全部放到后面去 int removeElement01(vector<int>& 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<int>& 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<int> sortedSquares(vector<int>& nums) { vector<int> 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<char>& 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<ListNode*> sA; stack<ListNode*> 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<ListNode*> 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) 多余容器空间
思路二：双指针
快指针走两步，慢指针走一步
时间复杂度：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)
思路二：快慢指针，慢的走一步，快的走两步
就是这个难，可以结合官方讲解和代码随想录的一起学习
时间复杂度：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<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> 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<int>{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<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> 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<int>{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; } };
