代码随想录-双指针

本章题目之前全都出现过，这里再写一遍进行复习；双指针法是很重要的解题思想，因此本章的题目都很重要（⭐⭐⭐）

移除元素（⭐）

LeetCode.27

核心代码：

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

反转字符串

LeetCode.344

核心代码：

void reverseString(vector<char>& s) {
    for(int i=0,j=s.size()-1;i<j;i++,j--){
        swap(s[i], s[j]);
    }
}

反转字符串中的单词

LeetCode.151

核心代码：

void removeExtraSpace(string& s) { // ⭐
    int slow = 0, fast = 0;
    for (; fast < s.size(); fast++) {
        if (s[fast] != ' ') {
            if (slow != 0) {
                s[slow] = ' ';
                slow++;
            }
            while (fast < s.size() && s[fast] != ' ') {
                s[slow++] = s[fast++];
            }
        }
    }
    s.resize(slow);
}
void reverse(string& s, int start, int end){
    for(int i=start,j=end;i<j;i++,j--){
        swap(s[i], s[j]);
    }
}
string reverseWords(string s) {
    removeExtraSpace(s);
    reverse(s,0,s.size()-1);
    int begin=0;
    for(int i=0;i<=s.size();i++){
        if(i==s.size()||s[i]==' '){
            reverse(s, begin, i-1);
            begin=i+1;
        }
    }
    return s;
}

反转链表

LeetCode.206

核心代码：

ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while(cur!=nullptr){
        ListNode* temp = cur->next;
        cur->next=pre;
        pre=cur;
        cur=temp;
    }
    return pre;
}

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

LeetCode.19

核心代码：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(0, head);
    ListNode* slow=dummyHead;
    ListNode* fast=dummyHead;
    for(int i=0;i<n;i++){
        fast=fast->next;
    }
    while(fast->next!=nullptr){   
        slow=slow->next;
        fast=fast->next;
    }
    slow->next=slow->next->next;
    return dummyHead->next;
}

相交链表（⭐）

LeetCode.160

核心代码：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA=0,lenB=0;
    ListNode* pA=headA;
    ListNode* pB=headB;
    while(pA!=nullptr){ // 求A链表长度
        lenA++;
        pA=pA->next;
    }
    while(pB!=nullptr){ // 求B链表长度
        lenB++;
        pB=pB->next;
    }
    pA=headA,pB=headB;
    int difference=0; // 求差值
    if(lenA>lenB){ // 让长表先走
        difference=lenA-lenB;
        while(difference--){
            pA=pA->next;
        }
    }else{
        difference=lenB-lenA;
        while(difference--){
            pB=pB->next;
        }
    }
    while(pA!=nullptr){
        if(pA==pB){
            return pA;
        }
        pA=pA->next;
        pB=pB->next;
    }
    return nullptr;
}

环形链表（⭐⭐⭐）

LeetCode.142

核心代码：

ListNode *detectCycle(ListNode *head) {
    ListNode* slow=head;
    ListNode* fast=head;
    while(fast!=nullptr&&fast->next!=nullptr){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){
            ListNode* index1=slow;
            ListNode* index2=head;
            while(index1!=index2){
                index1=index1->next;
                index2=index2->next;
            }
            return index1;
        }
    }
    return  nullptr;
}

三数之和（⭐⭐⭐）

LeetCode.15

核心代码：

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-1]==nums[i]){
            continue;
        }
        int left=i+1;
        int right=nums.size()-1;
        while(left<right){
            int tempSum=nums[i]+nums[left]+nums[right];
            if(tempSum>0){
                right--;
            }else if(tempSum<0){
                left++;
            }else if(tempSum==0){
                res.push_back({nums[i],nums[left],nums[right]});
                while(left<right&&nums[left]==nums[left+1]){
                    left++;
                }
                while(left<right&&nums[right]==nums[right-1]){
                    right--;
                }
                left++;
                right--;
            }
        }
    }    
    return res;
}

四数之和（⭐⭐）

LeetCode.18

核心代码：

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    for(int k=0;k<nums.size();k++){
        if(nums[k]>=0&&nums[k]>target){
            break; 
        }
        if(k>0&&nums[k]==nums[k-1]){
            continue;
        }
        for(int i=k+1;i<nums.size();i++){
            if(nums[i]+nums[k]>=0&&nums[i]>target-nums[k]){
                break;  // ⭐ 一定要用break，否则会漏掉结果
            } 
            if(i>k+1&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=nums.size()-1;
            while(left<right){
                long tempSum=(long)nums[k]+nums[i]+nums[left]+nums[right];
                if(tempSum>target){
                    right--;
                }else if(tempSum<target){
                    left++;
                }else{
                    res.push_back({nums[k],nums[i],nums[left],nums[right]});
                    // ⭐ 去重逻辑一定要在加入一个数对之后，否则[0,0,0,0]这种就直接漏掉了
                    while(left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
    }
    return res;
}