【双指针】早早开启双指针的大门
同向双指针 | 移动速度相同，一般同向移动 |
|---|---|
双向双指针 | 移动速度相同，一般相向移动 |
快慢双指针 | 移动速度不同 |
问题1：同向双指针：
【力扣】1. 两数之和
解题;
使用同向双指针，两个指针首先都指向第一个元素，然后先固定第一个指针，第二个指针向后遍历，判断两个指针指向的数组元素之和是否等于给定的目标和值，如果不等，等第二个指针遍历完后，第一个指针再向后移动一位，第二个指针再从第一个指针的位置向后遍历整个数组，以此类推。（有点像选择排序的过程）
时间复杂度:n+(n-1)+....+1=n*(n-1)/2
也就是o(n^2)
代码：（注意：代码并不一定能在力扣上跑）
int main()
{
int a[5] = { 1,2,3,4,5 };
int sz = sizeof(a) / sizeof(a[0]);
int key = 9;
for (int i = 0; i < sz - 1; i++)
{
for (int j = i;j < sz; j++)
{
if (a[i] + a[j] == key)
{
printf("在数组中%d和%d的和为%d\n",a[i],a[j],key);
}
}
}
return 0;
}对于同向指针：如果我要你删除链表倒数第n个结点（未知链表长度情况下，如果常规遍历要要先确定链表长度，然后做减法知道倒数第n个结点所在的正序位置，从而遍历到该位置），但是如果我们使用同向指针（只用遍历一遍，时间复杂度n，高效！）
解决办法：让指针1先遍历到第n个结点，然后指针2指向首元结点，然后两个指针以同样的速度向右移动，当指针1遇到尾结点停下来的时候，指针2也就自然地到了倒数第n个结点的位置。
问题2：双向双指针：(还是两数之和那题）
解题：
注意到该数组原本有序，因此要小心,再思考一下下
我们可以使第一个指针指向第一个元素(左指针），第二个指针指向最后一个元素（右指针），将指针指向的元素相加和目标和值比较，由于数组是有序的：
如果两指针指向的数组元素相加之和大于目标和值，就使右指针回退一位，左指针不动；
如果两指针指向的数组元素相加之和小于目标和值，就使左指针回退一位，右指针不动；
如果两指针指向的数组元素相加之和等于目标和值，就得到结果。
时间复杂度：o(n)
代码：
int main()
{
int a[5] = { 1,2,3,4,5 };
int sz = sizeof(a) / sizeof(a[0]);
int key = 7;
int left = 0, right = sz - 1;
while (left<right)
{
if (a[left] + a[right] > key) right--;
else if (a[left] + a[right] > key) left++;
else
{
printf("在数组中%d和%d的和为%d\n", a[left], a[right], key);
break;
}
}
return 0;
}
问题3：快慢双指针：
题目链接传送门【力扣】141. 环形链表
解题：
我们设置两个指针，一个快指针，一个慢指针，当慢指针走一步，快指针就走两步
如果链表没有环，那么快指针因为走的快，就会在链表的最后一个结点或者倒数第二个结点处停下来
如果链表有环，那么就会快指针因虽然走的快，但是因为有环，快指针和慢指针肯定会在环的某点(其实就是环的入口点)相遇
代码：
bool hasCycle(struct ListNode *head) {
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast->next!=NULL&&fast->next->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
{
return ture;
}
}
return false;
}腾讯云开发者
