双指针法

双指针是一种做题思路，并不隶属于某一种特定的数据结构，数组、链表、字符串都可以出双指针的题目

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)   多余容器空间

思路二：双指针

快指针走两步，慢指针走一步

正版双指针思路： https://leetcode-cn.com/problems/linked-list-cycle/solution/dai-ma-sui-xiang-lu-141-huan-xing-lian-b-h1jq/

时间复杂度：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;
                            [-] .\Navicat-Cracker NavicatCrackerDlg.cpp:332 -3All patch solutions are suppressed. Patch abort!HI

双指针法

27. 移除元素 【简单，快慢指针，首尾指针】

26. 删除有序数组中的重复项 【简单，快慢指针】

844. 比较含退格的字符串 【简单】

977. 有序数组的平方 【简单，首尾指针】

344. 反转字符串 【简单】

剑指 Offer 05. 替换空格 【简单，双指针】

151. 翻转字符串里的单词 【简单】

206. 反转链表 【简单】

19.删除链表的倒数第N个节点【简单】

160. 相交链表 【简单】

141. 环形链表 【简单，哈希表，双指针】

142. 环形链表 II 【中等】

15. 三数之和 【中等，双指针】

18. 四数之和 【中等】

27. 移除元素【简单，快慢指针，首尾指针】

26. 删除有序数组中的重复项【简单，快慢指针】

844. 比较含退格的字符串【简单】

977. 有序数组的平方【简单，首尾指针】

344. 反转字符串【简单】

剑指 Offer 05. 替换空格【简单，双指针】

151. 翻转字符串里的单词【简单】

206. 反转链表【简单】

160. 相交链表【简单】

141. 环形链表【简单，哈希表，双指针】

15. 三数之和【中等，双指针】

18. 四数之和【中等】