1.双指针
目录1.1 什么是双指针
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
1.2 对撞指针
对撞指针是指在数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。
对撞数组适用于连续数组和字符串，也就是说当你遇到题目给定连续数组和字符床时，应该第一时间想到用对撞指针解题
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
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 (left < right) {
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;
}
};
思路见代码回想录题解
视频
也算是对撞指针了
1.3 快慢指针
快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如 fast 每次增长两个，slow 每次增长一个。
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
原题
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) {
return head;
}
ListNode *dummy = new ListNode();
ListNode *tail = dummy;
while(head != NULL) {
while(head->next != NULL && head->val == head->next->val) {
head = head ->next;
}
if (head->next == NULL || head->val != head->next->val) {
tail ->next = head;
tail = head;
}
head = head->next;
}
tail->next = NULL;
return dummy->next;
}
};
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) {
return head;
}
ListNode *dummy = new ListNode();
ListNode *tail = dummy;
while (head != NULL) {
if (head->next == NULL || head->val != head->next->val) {
tail->next = head;
tail = head;
}
while (head->next != NULL && head->val == head->next->val) {
head = head->next;
}
head = head->next;
}
tail->next = NULL;
return dummy->next;
}
};
这两道题都是用了一个算是快慢指针的思想吧
基本思路：
几乎所有的链表题目，都具有相似的解题思路。
-
建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面
-
使用 tail 代表当前有效链表的结尾
-
通过原输入的 head 指针进行链表扫描
看题解可以看懂，但真的好难想到啊没搞明白...
还得再练练
