双指针总结

Algorithm-Double Pointer

Algorithm-Conclusion

07/25/2019

一、相向双指针

两根指针一头一尾，向中间靠拢直到相遇，时间复杂度 O(n) Two Sum 类：哈希表和双指针，双指针更快 Partition 类：

partition模板

PYTHON

while left <= right:
    while left <= right and nums[left] 应该在左侧:
        left +=1 
    while left <= right and nums[right] 应该在右侧:
        right -=1
    if left <= right:
        # 找到了一个不该在左侧的不该在右侧的，交换他们
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

二、同向双指针

两根指针一前一后，直到前面的指针走过头，时间复杂度 O(n)

Q&A

如果需要保证最少修改次数如何做？
使用 Partition 的方法可以做到交换次数最优
不需要维持相对顺序 vs 需要维持相对顺序算法有什么区别？
不需要维护相对顺序，可以使用 Partition 的方法，时空复杂度和交换次数都是最优的需要维护相对顺序的，只能使用同向双指针的方法，时空复杂度最优，但是交换次数不是最优的

题目

16. 3sum

3个数相加为0，循环第一个数，后面两个数用相向双指针

时间复杂度： $O(n^2)$ ，第一个数循环，k,j会遍历剩下的数，相当于2层循环
空间复杂度： $O(n^3)$ ，结果存储最多需要的空间

C++

class Solution {
private:
    void quicksort(vector<int>& nums, int left, int right) {
        if(right <= left) return;
        int begin = left;
        int end = right;
        int pivot = rand() % (right+1-left) + left;
        swap(nums[pivot], nums[right]);
        pivot = right--;
        while(right > left) {
            if(nums[left] <= nums[pivot]) {
                left++;
                continue;
            }
            if(nums[right] >= nums[pivot]) {
                right--;
                continue;
            }
            swap(nums[left++], nums[right]);
        }
        if(nums[left] < nums[pivot]) left++;
        swap(nums[pivot], nums[left]);
        quicksort(nums, begin, left-1);
        quicksort(nums, left+1, end);
    }
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() < 3) return res;
        quicksort(nums, 0, nums.size()-1);
        for(int i = 0; i < nums.size()-2; i++) {
            if(i && nums[i] == nums[i-1]) continue;
            int j = i+1;
            int k = nums.size()-1;
            while(k > j) {
                if(nums[i]+nums[j]+nums[k] < 0) {
                    j++;
                    continue;
                }
                if(nums[i]+nums[j]+nums[k] > 0) {
                    k--;
                    continue;
                }
                res.push_back({nums[i], nums[j], nums[k]});
                while(nums[j]==nums[++j] && k > j) continue;
                while(nums[k]==nums[--k] && k > j) continue;
            }
        }
        return res;
    }
};

153.Find Minimum in Rotated Sorted Array

查找最小数，数组是已排序的，只是翻转了一个位置，可以使用相向双指针做

时间复杂度： $O(n)$ ，遍历一遍
空间复杂度： $O(n)$ ，数组大小

C++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        if(nums[right] >= nums[left]) return nums[left];
        while(right > left) {
            if(nums[--right] >= nums[left]) return nums[++right];
        }
        return -1;
    }
};

16. 3Sum Closet

和3Sum类似，但是要用变量存储最小值，每次比较大小，更新

时间复杂度： $O(n^2)$ ，第一个数循环，k,j会遍历剩下的数，相当于2层循环
空间复杂度： $O(n)$ ，nums存储

C++

class Solution {
private:
    void quicksort(vector<int>& nums, int left, int right) {
        if(right <= left) return;
        int begin = left;
        int end = right;
        int pivot = rand() % (right+1-left) + left;
        swap(nums[pivot], nums[right]);
        pivot = right--;
        while(right > left) {
            if(nums[left] <= nums[pivot]) {
                left++;
                continue;
            }
            if(nums[right] >= nums[pivot]) {
                right--;
                continue;
            }
            swap(nums[left++], nums[right]);
        }
        if(nums[left] < nums[pivot]) left++;
        swap(nums[pivot], nums[left]);
        quicksort(nums, begin, left-1);
        quicksort(nums, left+1, end);
    }
public:
    int threeSumClosest(vector<int>& nums, int target) {
        auto size = nums.size();
        if(size < 3) return -1;
        quicksort(nums, 0, size-1);
        int res = nums[0]+nums[1]+nums[2];
        int distance = abs(res-target);
        int sum;
        for(int i = 0; i < size-2; i++) {
            if(i && nums[i]==nums[i-1]) continue;
            int j = i+1;
            int k = size-1;
            while(k > j) {
                sum = nums[i] + nums[j] + nums[k];
                if(abs(sum-target) < distance) {
                    distance = abs(sum-target);
                    res = sum;    
                }
                if(sum <= target) {
                    j++;
                } else if(sum > target) {
                    k--;
                }
            }
        }
        return res;
    }
};

19. Remove Nth Node From End of List

要求删除倒数第n个，可以使用快慢指针（同向双指针），fast走n次2步，如果还没到终点，就和slow一样每次走一步，到达终点，删除slow的next节点即可

时间复杂度：O(n)
空间复杂度：O(1)

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        while(n) {
            fast = fast->next;
            n--;
        }
        while(fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy->next;
    }
};

141. Linked List Cycle

用快慢指针

时间复杂度： $O(n)$
空间复杂度： $O(1)$

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head || !head->next) return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast != slow) {
            if(!fast || !fast->next) return false;
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

287. Find the Duplicate Number

使用快慢指针，因为总共有n+1个数，但是数字是1到n的，具体证明见另一篇总结

时间复杂度： $O(n)$ ，slow指针最多走n-1次
空间复杂度： $O(1)$

C++

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int i = nums[nums[0]];
        int j = nums[0];
        while(i != j) {
            i = nums[nums[i]];
            j = nums[j];
        }
        i = 0;
        while(i != j) {
            i = nums[i];
            j = nums[j];
        }
        return i;
    }
};

个人更多算法总结在Github

WRITTEN BY

pfan8

Monsgrammer

Email GitHub Facebook Twitter LinkedIn Medium