一、相向双指针
两根指针一头一尾，向中间靠拢直到相遇，时间复杂度 O(n) Two Sum 类：哈希表和双指针，双指针更快 Partition 类：
partition模板
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)\)，结果存储最多需要的空间
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)\)，数组大小
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存储
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)
/**
* 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)\)
/**
* 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)\)
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
